### 题目

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.

### 迭代遍历，用Stack缓存暂时剪下来的右子树

         1
/ \
2   5
/ \   \
3   4   6


         1                  | |
\                 |5|->6->null
2        stack:  |_|
/ \
3   4


         1                  |4|->null
\                 |5|->6->null
2        stack:  |_|
\
3


         1                  | |
\                 |5|->6->null
2        stack:  |_|
\
3
\
4


         1                  | |
\                 | |
2        stack:  |_|
\
3
\
4
\
5
\
6


#### 代码

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public void flatten(TreeNode root) {
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur.left != null || cur.right != null) {
if (cur.left != null) {
if (cur.right != null) {
stack.offerFirst(cur.right);
}
cur.right = cur.left;
cur.left = null;
}
cur = cur.right;
}
cur.right = stack.pollFirst();
cur = cur.right;
}
}
}


### 分治法，深度优先递归

1. 把左子树铺平，嫁接到右子树。
2. 把右子树铺平，嫁接到已经铺平的左子树的右子树。

#### 代码

public void flatten(TreeNode root) {
flattenRecur(root);
}
public TreeNode[] flattenRecur(TreeNode root) {
if (root == null) { return headTail; }
TreeNode[] leftSub = flattenRecur(root.left);
TreeNode[] rightSub = flattenRecur(root.right);
TreeNode cur = root;
if (leftSub[0] != null) { cur.left = null; cur = grafting(cur,leftSub); }
if (rightSub[0] != null) { cur = grafting(cur,rightSub); }
}
// graft target as the right subtree of root.
// return the tail of the target
public TreeNode grafting(TreeNode root, TreeNode[] target) {
TreeNode cur = root;
cur.right = target[0];
return target[1];
}


### 简化上面的分治递归

#### 代码

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public void flatten(TreeNode root) {
flattenRecur(root,null);
}
public TreeNode flattenRecur(TreeNode root, TreeNode pre) {
if (root == null) { return pre; }
TreeNode cur = root;
pre = flattenRecur(root.right,pre);
pre = flattenRecur(root.left,pre);
root.left = null;
root.right = pre;
return root;
}
}