Leetcode日记:114.展平一个二叉树

题目

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

1
2
3
4
5
    1
/ \
2 5
/ \ \
3 4 6

The flattened tree should look like:

1
2
3
4
5
6
7
8
9
10
11
1
\
2
\
3
\
4
\
5
\
6

题目分析

这道题我刚拿到手里是一脸懵逼的,这怎么做啊。直到看见官方提示:

1
2
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.
如果仔细观察展开后的树,每个节点的右子节点指向一个先序遍历的下一个节点。

这意味着,我们需要有先序遍历的思路

代码

一般思路代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 public class Solution {
public void flatten(TreeNode root) {
if(root==null)
return;
flatten(root.left);
flatten(root.right);
TreeNode left = root.left;
TreeNode right = root.right;
root.left = null;
root.right = left;
while(root.right!=null)
root = root.right;
root.right = right;
}
}

超简洁版代码

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
private TreeNode prev = null;
public void flatten(TreeNode root) {
if (root == null)
return;
flatten(root.right);
flatten(root.left);
root.right = prev;
root.left = null;
prev = root;
}
}

解题思路

代码1解析

很明显的DFS思想,假设原来的树是:

1
2
3
4
5
6
7
    1            1
/ \ / \
2 5 2 5
/ \ \ \ \
3 4 6 3 6
\
4

然后,进入第一次flatten(root.left);,这时,首先创建两个新节点leftright,分别把当前左节点和右节点赋给他们,防止覆盖,然后直接令当前左节点为null,当前右节点换成左节点,随后顺着右面的岔路一直向右,在右路的尽头添加右节点。变成下面的样子:

其实我们看上去5和6直接是相连的,但是我们在程序上仍然对他们两个进行了排序,只不过排序之前和排序之后是一样的。所以接下来直接执行最后一条,这样我们可以看出来,我们已经把下面所有的树都已经排好序(展开),只差最上面一层了

所以代码1的思路是先利用DFS的思路找到最左子节点,然后回到其父节点,把其父节点和右子节点断开,将原左子结点连上父节点的右子节点上,然后再把原右子节点连到新右子节点的右子节点上,然后再回到上一父节点做相同操作。

更加优雅的代码2

有没有发现,代码2是从右面开始DFS的?这就是他优雅的所在,因为他遍历的是右面,导致省了一个循环。这个循环本是应该正向搜索时寻找右节点的放置位置。

1
2
3
root.right = prev;
root.left = null;
prev = root;

这几行代码保证了将最右的节点永远是他前面节点的右节点。

具体流程是这样的:

1
2
3
4
5
6
7
    1            1
/ \ / \
2 5 2 5
/ \ \ \ \
3 4 6 3 6
\
4

总结

这道题在没有前序遍历,后序遍历,中序遍历树的知识前遇见是挺难受的,一直不想面对树这个数据结构,有点阴影,但是没有办法,回溯到DFS都和树这个结构有着很大的联系,下面可能要学习一下遍历的知识了。等到学完,再更新补全。