leetcode114.Flatten Binary Tree to Linked List

发表于 更新于 分类于 ，

题目要求

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

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6
The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6
click to show hints.

Hints:
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

将一棵二叉树展开形成一棵链表形状的树。本质上是将该树转变成先序遍历后的样子。

思路一：非递归##

如果我们从图形的角度来说，每一次都将当前节点的右子树拼接到左子节点的右子树下，再将左节点替换原来的右节点。所以这个例题一步步的操作如下：

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

代码如下：

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

思路二：递归

其实这里的思路等价于反转的先序遍历。自底向上深度优先遍历，这要求将前序遍历的头结点通过临时变量保存一下。代码如下：

1
2
3
4
5
6
7
8
9
TreeNode pre = null;
public void flatten2(TreeNode root) {
    if(root==null) return;
    flatten(root.right);
    flatten(root.left);
    root.left = null;
    root.right = pre;
    pre = root;
}