題目描述
將一棵二叉樹按照前序遍歷拆解成為一個?假鏈表摘盆。所謂的假鏈表是說坝冕，用二叉樹的?right?指針欢峰，來表示鏈表中的?next?指針梨树。
不要忘記將左兒子標記為 null坑夯，否則你可能會得到空間溢出或是時間溢出。
測試樣例
輸入：{1,2,5,3,4,#,6}
輸出：{1,#,2,#,3,#,4,#,5,#,6}
解釋：
? ? 1
? ? / \
? 2? 5
? / \? \
3? 4? 6
1
\
2
? \
? 3
? ? \
? ? 4
? ? ? \
? ? ? 5
? ? ? ? \
? ? ? ? 6
輸入：{1}
輸出：{1}
解釋：
? ? ? ? 1
? ? ? ? 1
解題思路與方法
1. Devide & Conquer
分冶法實現(xiàn)起來十分簡潔抡四，同時不增加額外的空間消耗柜蜈。
對于每個節(jié)點，先分別處理左子樹與右子樹指巡，待左淑履、右子樹處理完畢，分別獲得它們先序遍歷的最后一個葉子節(jié)點藻雪，分別記為 left_last 和 right_last秘噪。
若左子樹返回的最后一個葉子節(jié)點存在，那么將其連接到右子樹勉耀，即將這個節(jié)點的右兒子設(shè)為當前節(jié)點的右兒子指煎。同時，將當前節(jié)點的右兒子設(shè)為其左兒子便斥，然后將其左兒子設(shè)為空至壤。
最后，若right_last存在枢纠，則返回它像街，否則，若left_last存在晋渺，返回它镰绎，否則，返回這個節(jié)點本身些举。
2. 利用堆棧進行先序遍歷
該方法需要一個堆棧來存放先序遍歷過程中遇到的節(jié)點跟狱，初始時將根節(jié)點入棧。
接著進入一個循環(huán)直至棧為空户魏，每次循環(huán)彈出棧頂節(jié)點驶臊，然后先將該節(jié)點的右兒子（若有的話）入棧挪挤，然后才是左兒子（若有的話）。
下一步关翎，將當前節(jié)點的左兒子設(shè)為空扛门，而右兒子設(shè)為棧頂節(jié)點，若棧為空纵寝，則右兒子設(shè)為空论寨。
這樣，一輪循環(huán)就完成了爽茴，重復(fù)這種操作直至椩岬剩空即可。
代碼
1. Devide & Conquer
"""
Definition of TreeNode:
class TreeNode:
? ? def __init__(self, val):
? ? ? ? self.val = val
? ? ? ? self.left, self.right = None, None
"""
class Solution:
? ? """
? ? @param root: a TreeNode, the root of the binary tree
? ? @return: nothing
? ? """
? ? def flatten(self, root):
? ? ? ? if not root:
? ? ? ? ? ? return
? ? ? ? # 左子樹最后一個葉子節(jié)點
? ? ? ? left_last = self.flatten(root.left)
? ? ? ? # 右子樹最后一個葉子節(jié)點
? ? ? ? right_last = self.flatten(root.right)
? ? ? ? # 把左子樹的最后一個葉子節(jié)點連接到右子樹
? ? ? ? if left_last:
? ? ? ? ? ? left_last.right = root.right
? ? ? ? ? ? root.right = root.left
? ? ? ? ? ? root.left = None
? ? ? ? # 注意這里的返回順序室奏，應(yīng)該是右子樹->左子樹->節(jié)點本身
? ? ? ? return right_last or left_last or root
2. 利用堆棧進行先序遍歷
class Solution:
? ? """
? ? @param root: a TreeNode, the root of the binary tree
? ? @return: nothing
? ? """
? ? def flatten(self, root):
? ? ? ? if not root:
? ? ? ? ? ? return
? ? ? ? stack = [root]
? ? ? ? while stack:
? ? ? ? ? ? node = stack.pop()
? ? ? ? ? ? '''先序遍歷時火焰，先將右兒子入棧，再將左兒子入棧'''
? ? ? ? ? ? if node.right:
? ? ? ? ? ? ? ? stack.append(node.right)
? ? ? ? ? ? if node.left:
? ? ? ? ? ? ? ? stack.append(node.left)
? ? ? ? ? ? node.left = None
? ? ? ? ? ? node.right = stack[-1] if stack else None
