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

For example,
Given 

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

Hints:

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

思路

我们根据题目的提示，知道了flattened tree的组织形式是基于先根序遍历的。那我们可以利用后根序遍历来构造这棵flattened tree。后序遍历节点，依次将遍历到的第n+1个节点指向第n个节点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode next = null;
    public void postorder(TreeNode root){
        if(root != null){
            postorder(root.right);
            postorder(root.left);
            if(next != null){
                root.right = next;
                root.left = null;
            }
            next = root;
        }
    }
    public void flatten(TreeNode root) {
        postorder(root);
    }
}