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

题目

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

For example, given the following tree:

The flattened tree should look like:

题目分析

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

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.
如果仔细观察展开后的树，每个节点的右子节点指向一个先序遍历的下一个节点。

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

代码

一般思路代码

 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;
    }
}

超简洁版代码

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            1
   / \          / \
  2   5        2   5
 / \   \        \   \
3   4   6        3   6  
                   \
                    4

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

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

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

更加优雅的代码2

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

1
2
3

root.right = prev;
root.left = null;
prev = root;

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

具体流程是这样的：

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

总结

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