114. 二叉樹展開為鏈表
題目來源：力扣（LeetCode）
https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
題目
給定一個二叉樹，原地將它展開為一個單鏈表刻像。
例如，給定二叉樹
1
/ \
2 5
/ \ \
3 4 6
將其展開為：
1
\
2
\
3
\
4
\
5
\
6
解題思路
思路： 遞歸，非遞歸
遞歸
我們先觀察例子尽爆，可以發(fā)現(xiàn)谣旁，左子樹展開成鏈表連接在根節(jié)點秦陋，而右子樹展開鏈表是緊跟在左子樹展開的鏈表后面惠呼。這里使用遞歸的方法來解決佩番。
使用后序遍歷（遞歸）的具體做法：
- 先找到左子樹的最右節(jié)點；
- 當(dāng)找到左子樹的最右節(jié)點時罢杉，令其指向根的右子樹；
- 此時贡歧，再讓根的右子樹滩租，指向根節(jié)點的左子樹；
- 最后利朵，令根節(jié)點的左子樹為 None律想，循環(huán)直至右子樹為空。
具體的代碼見【代碼實現(xiàn) # 遞歸】
非遞歸
在前面我們知道绍弟，其實遞歸的思路技即，使用了額外的空間。這里樟遣，我們使用非遞歸的方法來嘗試解決而叼。（具體做法同上）
具體的代碼見【代碼實現(xiàn) # 非遞歸】
代碼實現(xiàn)
# 遞歸
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
def unflod(node):
if not node:
return None
unflod(node.left)
unflod(node.right)
# 后序遍歷
if node.left:
pre = node.left
# 找到左子樹的最右子節(jié)點，用以連接根的右子樹
while pre.right:
pre = pre.right
# 當(dāng)找到左子樹的最右子節(jié)點豹悬，令其指向根的右子樹
pre.right = node.right
# 然后令根的右子樹指向根的左子樹葵陵，令根的左子樹為空
node.right = node.left
node.left = None
# 循環(huán)
node = node.right
unflod(root)
# 非遞歸
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
while root:
if root.left:
pre_node = root.left
# 同樣先找到左子樹的最右節(jié)點
while pre_node.right:
pre_node = pre_node.right
# 最右節(jié)點指向根節(jié)點的右子樹
pre_node.right = root.right
# 根的右子樹指向根的左子樹，同時置空左子樹
root.right = root.left
root.left = None
root = root.right
實現(xiàn)結(jié)果
實現(xiàn)結(jié)果 | 遞歸
實現(xiàn)結(jié)果|遞歸
實現(xiàn)結(jié)果 | 非遞歸
實現(xiàn)結(jié)果 | 非遞歸
歡迎關(guān)注
公眾號 【書所集錄】
