题目描述
给定一个二叉树的根节点，将它展开为一个单链表
- 展开后的单链表，同样使用
TreeNode，其中right指针指向链表下一个节点，left指针始终为null - 展开后的单链表应该与二叉树的前序遍历的顺序相同
思路
前序遍历的访问节点的顺序为：根 -> 左 -> 右
则根节点访问后，应该先访问左子树，左子树访问完毕后，再访问右子树。
访问左子树时，同样按照 [根 -> 左 -> 右] 的顺序，左子树中第一个被访问的点应当是左子树的根节点。
所以根节点若存在左子树，则应当将左子树整个接到根节点的right指针上。那么根节点的右子树应当如何处理呢？我们知道右子树中第一个被访问的仍然是右子树的根节点。而只有当左子树全部访问完毕后，才会访问右子树。那么，应当将根节点的右子树，接到根节点左子树上最后一个被访问的点。
由于在左子树上，我们仍然是按照 [根 -> 左 -> 右] 的顺序来访问节点。所以左子树上，最后一个被访问的节点，是左子树上最右侧的节点，这个节点也是根节点的前驱结点。
但是我们在代码实现时，不需要真正找到左子树上的最后一个被访问的节点，我们只需要从左子树上一直往右侧找，找到第一个不存在右儿子的节点last，然后将根节点的右子树，整个接到这个last节点的right指针上即可。（实际根节点左子树上最后一个被访问的节点，应当是last节点左子树上最后一个被访问的节点）
因为我们在左子树上，是一直往右侧找的，在找的过程中，只要存在右儿子，则右儿子所在的子树，其访问顺序一定是靠后的（因为前序遍历[根 -> 左 -> 右] 的访问顺序），而当找到一个不存在右儿子的节点时，这个节点所在的子树，一定是先访问往该节点的左子树，再访问其右子树，而我们后面进行展开时，也是按照前序遍历的规则来展开，这样就能保证，访问的相对顺序不变。
即，由于我们是按照前序遍历进行展开，在后面的处理中，我们能保证，先访问last节点，然后展开last节点的左子树，其左子树全部访问完毕后，再展开last节点的右子树，所以我们不需要一次性的将根节点的右子树接到其最终的位置 。留到后面进行处理即可。
根据上面的思路，给出我们的算法流程：
-
从根节点开始，判断当前节点是否存在左儿子
-
当前节点往右走
class Solution {
public void flatten(TreeNode root) {
while (root != null) {
if (root.left != null) {
TreeNode last = root.left;
while (last.right != null) last = last.right;
last.right = root.right;
root.right = root.left;
root.left = null;
}
root = root.right;
}
}
}
扩展
既然题目要求按照前序遍历展开为链表，那么进一步，我们能不能按照中序和后序遍历的顺序展开呢？答案是可以的。
按照中序遍历展开
同样的，中序遍历的节点访问顺序是 [左 -> 根 -> 右] 。根据这个顺序，我们知道，根节点是在中间被访问的，根节点访问后访问右子树，则 根节点和右子树的关系先不用动。我们来看左子树。我们需要找到左子树上最后一个被访问的节点，这个节点的下一个节点就是根节点。由于访问顺序是[左 -> 根 -> 右]，右子树仍然是后被访问的，所以我们仍然在左子树上，一直往右找，直到找到一个不存在右儿子的节点last，对于这个last节点所在的子树，由于访问顺序是 [左 -> 根 -> 右]，而last节点不存在右儿子，则last节点就是最后被访问的节点了，也就是，此时找到的last，是左子树上真正的最后一个被访问的节点。那么我们需要把根节点，接到这个last节点的right指针上，然后把根节点的left指针置空，再更新当前节点为根节点的原左儿子。
当然，若根节点不存在左儿子，那么将当前节点往右走即可。
如此，我们的算法流程就是
从根节点开始，判断当前节点是否存在左子树
class Solution {
public void flatten(TreeNode root) {
TreeNode newHead = null;
while (root != null) {
if (root.left == null) {
root = root.right;
} else {
TreeNode last = root.left;
TreeNode nextRoot = root.left;
while (last.right != null) last = last.right;
last.right = root;
root.left = null;
root = nextRoot;
newHead = root;
}
}
while (newHead != null) {
System.out.printf("%d -> ", newHead.val);
newHead = newHead.right;
}
}
}
按照后序遍历展开
类似的，后序遍历的访问顺序是 [左 -> 右 -> 根]。
根节点是最后访问的，所以我们需要将根节点，接到右子树上最后一个被访问的节点之后。右子树上最后一个被访问的节点，是右子树的根节点。所以就要把根节点，接到其右儿子的right指针上。但我们怎么维护右儿子原先的right指针呢？并且，若根节点存在左子树，我们还要将左子树的最后一个访问的节点，和右子树第一个访问的节点连接起来。想了很久感觉都是很难去实现的。
但是我们可以换一种思路，我们逆序，按照 [根 -> 右 -> 左] 的顺序来进行展开，展开完毕后再做一次链表翻转即可。这样的话，思路就和前序遍历展开差不多了。
我们需要在根节点的右子树上，找到最后一个被访问的点，然后将根节点的左子树，整个接到这个点上即可。
class Solution {
public void flatten(TreeNode root) {
TreeNode head = root;
while (root != null) {
TreeNode l = root.left, r = root.right;
if (l != null) {
if (r == null) root.right = l;
else {
TreeNode last = r;
while (last.left != null) last = last.left;
last.left = l;
}
root.left = null;
}
root = root.right;
}
TreeNode cur = head, pre = null;
while (cur != null) {
TreeNode nextCur = cur.right;
cur.right = pre;
pre = cur;
cur = nextCur;
}
head = pre;
while (head != null) {
System.out.printf("%d -> ", head.val);
head = head.right;
}
}
}
小结
总结一下，此类题目都是考察了二叉树的遍历。对于一棵树，我们可以先将其切断，分成根节点，左子树，右子树，三部分来看。由于我们遍历时，实际每次只能处理当前的根节点，所以我们需要关注根节点和左右子树的相对访问顺序。然后根据需要，找到左子树，或者右子树上的第一个，或者最后一个被访问的节点，然后进行连接（注意，有时不需要找到真正的最后一个被访问的节点，也能保证答案的正确性，因为我们是按照既定的遍历顺序进行展开，只要我们的连接操作，不违反这个既定顺序，即可在后面的处理中，完成正确的展开（即，有时不能立即完成最终的顺序构造，而是生成了一些中间状态，只要保证这个中间状态不违反我们的既定遍历顺序，即可在后面的处理中对其进行正确构造））。
|