思想
二叉樹的核心思想是分治和遞歸，特點是遍歷方式。
解題方式常見兩類思路：
- 遍歷一遍二叉樹尋找答案；
- 通過分治分解問題尋求答案；
遍歷分為前中后序，本質(zhì)上是遍歷二叉樹過程中處理每個節(jié)點的三個特殊時間點：
- 前序是在剛剛進入二叉樹節(jié)點時執(zhí)行；
- 后序是在將要離開二叉樹節(jié)點時執(zhí)行；
- 中序是左子樹遍歷完進入右子樹前執(zhí)行；
# 前序
1 node
/ \
2 left 3 right
中左右
# 中序
2 node
/ \
1 left 3 right
左中右
# 后序
3 node
/ \
1 left 2 right
左右中
多叉樹只有前后序列遍歷，因為只有二叉樹有唯一一次中間節(jié)點的遍歷
題目的關(guān)鍵就是找到遍歷過程中的位置，插入對應(yīng)代碼邏輯實現(xiàn)場景的目的。
實例
二叉樹展開為鏈表 leetcode 114
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
輸入：
root: TreeNode，二叉樹的根節(jié)點
輸出：
root: TreeNode，完成二叉樹鏈表方式展開，返回根節(jié)點。展開方式是每個節(jié)點的左子樹為空，右子樹是下一個節(jié)點，節(jié)點順序符合前序遍歷順序。
舉例：
給定二叉樹 [1,2,5,3,4,null,6]
翻轉(zhuǎn)返回，[1,null,2,null,3,null,4,null,5,null,6]
1
/ \
2 5
/ \ / \
3 4 6
=>
1
\
2
\
3
\
4
\
5
\
6
二叉樹的數(shù)據(jù)存儲可以使用鏈表，也可以使用數(shù)組，往往數(shù)組更容易表達，根節(jié)點從 index=1 處開始存儲，浪費 index=0 的位置
left_child = 2 * parent
right_child = 2 * parent + 1
parent = child // 2
分治解
拆解為基礎(chǔ)問題：一個節(jié)點和已經(jīng)展開為鏈表的左右子樹節(jié)點。
如果要進行當前節(jié)點的鏈表展開，需要先獲得左右子樹節(jié)點的鏈表展開，所以邏輯控制應(yīng)該放在后序遍歷的位置。
從左子樹開始判斷，如果存在則將當前節(jié)點的左子樹置空，右子樹設(shè)置為左子樹的鏈表展開頭結(jié)點。
接著在拼接當前節(jié)點右子樹前，需要先沿著左子樹的展開鏈表走到末端，將這個節(jié)點的右子樹設(shè)置為當前節(jié)點的右子樹。
上例中，以根節(jié)點 1 為例，假設(shè)左右子樹分別完成了鏈表展開，返回了鏈表展開的頭結(jié)點。
1
/ \
2 5
\ \
3 6
\
4
- 將左右子樹頭結(jié)點先存儲，left = 1.left, right = 1.right，這樣后續(xù)方便操作 1 的左右子樹替換；
- 首先判斷 left not None，此時設(shè)置 1.left = None, 1.right = left；
1
\
2 <- 當前位置
\
3
\
4
- 然后將當前位置指向左子樹鏈表展開的末端 4
1
\
2
\
3
\
4 <- 當前位置
- 接著判斷 right not None，此時設(shè)置當前節(jié)點的右子樹是 right，4.right = right
1
\
2
\
3
\
4
\
5
\
6
編碼
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def flatten_binary_tree_to_linked_list(root: Optional[TreeNode]) -> Optional[TreeNode]:
# base 條件，空節(jié)點直接返回
if root is None:
return None
left = flatten_binary_tree_to_linked_list(root.left)
right = flatten_binary_tree_to_linked_list(root.right)
# 后序遍歷位置，離開節(jié)點的時候，獲得了左右子樹的全部信息，此時方便展開判斷
# 標記當前頭結(jié)點，用作最后返回
rtn = root
if left is not None:
root.left = None
root.right = left
# root 節(jié)點從當前左子樹打平鏈表的開頭移動到結(jié)尾
while root.right is not None:
root = root.right
if right is not None:
root.left = None
root.right = right
return rtn
相關(guān)
二叉樹 0
二叉樹 1
二叉樹 2
二叉樹 3
二叉樹 4
二叉樹 5
二叉樹 6
二叉樹 7
二叉樹 8
二叉樹 9
二叉樹 10
