LeetCode 114 Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
Hints:
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.
我以为我可以秒了tree遍历相关的题目。。。然而我还是天真了。。。特别是对应什么时候应该直接dfs，什么时候要写helper函数进行dfs这个问题，老是无法将intuition转化成code。。。
真的还需要多练习。。。有点心累。。。
思路挺简单的，但我一开始纠结于node情况的分类，其实分类非常简单！！！
只要判断左儿子是否为空就可以了！！！
左儿子不为空则插入到node与右儿子之间！！！
左儿子为空则直接return！！！
当然还有一个问题！！！
到底在什么时候调用递归函数？？？
按照前序中序后序遍历，调用递归的位置各不相同。
那这道题如hint所示，最终的形态与前序结果相同，那是不是应该在最开始操作，然后再调用递归呢？
思考后发现还是略有不同！
本题要做的操作是这样的：
首先希望左子树与右子树都已经被flatten，在此基础上，判断左儿子，然后决定如何重构root与root.left和root.right的关系。
这么看来，就应该先flatten(root.left)，再flatten(root.right)，最后再重构root和root.left和root.right。
重构时有一个trick就是，必须先iteration找到左儿子最右侧的leaf，然后将这个leaf.next设为root.right。
在判断是可以用node!=null && node.next!=null这个条件，判断node=null这个corner case！！！
代码：
public class Solution {
public void flatten(TreeNode root) {
if (root == null) return;
flatten(root.left);
flatten(root.right);
TreeNode rightmost = root.left;
while (rightmost != null && rightmost.right != null) {
rightmost = rightmost.right;
}
if (rightmost == null) return;
else {
rightmost.right = root.right;
root.right = root.left;
root.left = null;
}
}
}
