Given a binary tree, flatten it to a linked list in-place.
For example,
Given1 / \ 2 5 / \ \ 3 4 6
The flattened tree should look like:
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.
上面是题目及提示信息，大概意思是要按照前序遍历的顺序，将其变成一个但链表（但还是用树结构存），OK，开始分析下：
按照题目要求，它要把左子树的所有节点按照前序的顺序，挂载在右子树的链表中，那么我们首先遇到的第一个问题，把左子树挂载在右边，那之前的跟节点的右子树怎么处理？
上面这个问题，可以这样思考，我们假设已经把左子树挂载在右边，先忽视之前根节点的右子树，那么现在需要把其加载进去，那显然按照前序遍历的思想，我们肯定是把右子树挂载在左子树前序遍历的最后一个元素中，OK，这是我们目前的想法。
再思考下，我们只是简单的将根节点的左子树挂载在它和它的右子树中间，并没有将其“捋平”，这样就涉及到递归的处理，反复的将其，加进去。那这样就涉及到刚开始的一个问题，我们是否真的需要把右子树搁在左子树前序遍历的最后一个元素中？如下图所示，这里显然，我们只需要将4 搁在2的右子树位置上，（第二张图），然后再递归的捋顺根节点的right即可
1 1
2 4 2
3 5 6 3 4
5 6
因此，我们可以写出以下代码：
public void flatten(TreeNode root) { if (root == null) return; if (root.left != null) { TreeNode cur = root.left; while (cur.right != null) { cur = cur.right; } cur.right = root.right; root.right = root.left; root.left = null; } flatten(root.right);} 我们可以发现，最后的递归，特别像循环，因此可以消递归，优化代码，如下
public void flatten(TreeNode root) { while(root != null){ if(root.left != null){ TreeNode cur = root.left; while(cur.right != null){ cur = cur.right; } cur.right = root.right; root.right = root.left; root.left = null; } root = root.right; } }