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函數(shù)進行dfs這個問題痪伦，老是無法將intuition轉化成code侄榴。雹锣。癞蚕。
真的還需要多練習。桦山。恒水。有點心累。寇窑。甩骏。
思路挺簡單的先慷，但我一開始糾結于node情況的分類，其實分類非常簡單８Ｇ唷ＥЧ睢！
只要判斷左兒子是否為空就可以了Ｏ艹佟＝还摺！
左兒子不為空則插入到node與右兒子之間Ｒ饣纭！玖像！
左兒子為空則直接return＞嫣佟Ｓ濉碴里！
當然還有一個問題Ｉ险妗！根竿！
到底在什么時候調用遞歸函數(shù)？寇壳？妻怎？
按照前序中序后序遍歷，調用遞歸的位置各不相同匿辩。
那這道題如hint所示榛丢，最終的形態(tài)與前序結果相同，那是不是應該在最開始操作晰赞，然后再調用遞歸呢掖鱼？
思考后發(fā)現(xiàn)還是略有不同！
本題要做的操作是這樣的：
首先希望左子樹與右子樹都已經被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;
}
}
}
