114 二叉树展开为链表

1
2
3
4
5
6
7

1. 先序遍历
	利用 O(n) 额外空间的 list 来存先序遍历的每一个节点，然后利用 list 来还原结果
    
2. 寻找前驱节点
	利用 O(1) 空间，对于每个节点，找到其左子树的最右边节点，作为前驱节点，将右子树放到前驱节点后，迭代方式。
    
3. 利用后序遍历，递归方式。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// 方式3
public void flatten(TreeNode root) {
    if (root == null)
        return;
    flatten(root.left);
    flatten(root.right);
    TreeNode left = root.left;
    TreeNode right = root.right;
    // concat list
    root.right = left;
    root.left = null;
    TreeNode p = root;
    while (p.right != null) {
        p = p.right;
    }
    p.right = right;
}