思想
二叉樹的核心思想是分治和遞歸抵皱，特點(diǎn)是遍歷方式呻畸。
解題方式常見兩類思路：
- 遍歷一遍二叉樹尋找答案伤为；
- 通過分治分解問題尋求答案据途；
遍歷分為前中后序，本質(zhì)上是遍歷二叉樹過程中處理每個(gè)節(jié)點(diǎn)的三個(gè)特殊時(shí)間點(diǎn)：
- 前序是在剛剛進(jìn)入二叉樹節(jié)點(diǎn)時(shí)執(zhí)行位衩；
- 后序是在將要離開二叉樹節(jié)點(diǎn)時(shí)執(zhí)行便脊；
- 中序是左子樹遍歷完進(jìn)入右子樹前執(zhí)行光戈；
# 前序
1 node
/ \
2 left 3 right
中左右
# 中序
2 node
/ \
1 left 3 right
左中右
# 后序
3 node
/ \
1 left 2 right
左右中
多叉樹只有前后序列遍歷久妆，因?yàn)橹挥卸鏄溆形ㄒ灰淮沃虚g節(jié)點(diǎn)的遍歷
題目的關(guān)鍵就是找到遍歷過程中的位置跷睦，插入對(duì)應(yīng)代碼邏輯實(shí)現(xiàn)場(chǎng)景的目的抑诸。
實(shí)例
填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針 leetcode 116
class TreeNode:
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
輸入：
root: TreeNode，二叉樹的根節(jié)點(diǎn)
輸出：
root: TreeNode奸绷，完成二叉樹每個(gè)節(jié)點(diǎn)的 next 指針填充号醉，返回根節(jié)點(diǎn)
舉例：
給定二叉樹 [1,2,3,4,5,6,7]
翻轉(zhuǎn)返回辛块，[1,#,2,3,#,4,5,6,7,#]
1 1 -> None
/ \ / \
2 3 => 7 -> 2 -> None
/ \ / \ / \ / \
4 5 6 7 9->6->3->1 -> None
二叉樹的數(shù)據(jù)存儲(chǔ)可以使用鏈表，也可以使用數(shù)組线椰，往往數(shù)組更容易表達(dá)尘盼，根節(jié)點(diǎn)從 index=1 處開始存儲(chǔ)，浪費(fèi) index=0 的位置
left_child = 2 * parent
right_child = 2 * parent + 1
parent = child // 2
遍歷解
這個(gè)題目有兩個(gè)關(guān)鍵點(diǎn)：
- 識(shí)別各層莱衩，這個(gè)在之前的文章中有分析娇澎，不再贅述趟庄，重點(diǎn)是判斷當(dāng)前節(jié)點(diǎn)入隊(duì)的高度和當(dāng)前高度是否匹配戚啥，相等說(shuō)明進(jìn)入了新的一層锉试，因?yàn)閷?duì)左右子樹入隊(duì)的操作時(shí)都將層高加了 1；
- 每層最后的節(jié)點(diǎn)如何統(tǒng)一處理拖云，設(shè)置為 None。這里一種常用的思路是
占位乏苦，即當(dāng)識(shí)別到進(jìn)入新的一層時(shí)尤筐，在本層入隊(duì)新的節(jié)點(diǎn)前，先插入一個(gè) None 的節(jié)點(diǎn)掀淘，用作上層最后一個(gè)節(jié)點(diǎn)的 next 指向油昂。
分治解
將問題還原成最基礎(chǔ)的狀態(tài)：如果想要指向右側(cè)節(jié)點(diǎn)，一定需要含有兩個(gè)節(jié)點(diǎn)進(jìn)行遞歸稠腊。
兩個(gè)節(jié)點(diǎn)有兩種情況：
1.當(dāng)前節(jié)點(diǎn)的左右子樹節(jié)點(diǎn)鸣哀；
2.兩個(gè)同層相鄰節(jié)點(diǎn)的左右子樹相連節(jié)點(diǎn)。
所以遞歸的處理下一層這兩種子節(jié)點(diǎn)的相鄰關(guān)系我衬，然后本層將收到的兩個(gè)節(jié)點(diǎn)關(guān)聯(lián)即可挠羔。
編碼
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
def populating_next_right_pointers_in_each_node(root: Optional[TreeNode]) -> Optional[TreeNode]:
# 初始化
level_queue = []
height = 0
if root is not None:
level_queue.insert(0, (height, root))
# 遍歷求解
while level_queue:
cur_height, cur_node = level_queue.pop()
if cur_node is None:
continue
# 前序位置
if cur_height == height:
# 進(jìn)入新一層破加，占位 None 節(jié)點(diǎn)，用作上一層尾部對(duì)象的 next 指向
level_queue.insert(0, (height, None))
height += 1
if cur_node.left:
level_queue.insert(0, (height, cur_node.left))
if cur_node.right:
level_queue.insert(0, (height, cur_node.right))
# 后序位置范舀，當(dāng)前節(jié)點(diǎn)指向隊(duì)列最后一個(gè)元素的節(jié)點(diǎn)
cur_node.next = level_queue[-1][1]
return root
def populating_next_right_pointers_in_each_node_recursive(root: Optional[TreeNode]) -> Optional[TreeNode]:
def traverse(node1: TreeNode, node2: TreeNode):
# base 條件锭环，任意節(jié)點(diǎn)為空，無(wú)序處理
if node1 is None or node2 is None:
return
# 前序位置辅辩，將傳入兩個(gè)節(jié)點(diǎn)串聯(lián)
node1.next = node2
# 連接相同父節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)
traverse(node1.left, node1.right)
traverse(node2.left, node2.right)
# 連接跨越父節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)
traverse(node1.right, node2.left)
# 邊界保護(hù)
if root is None:
return None
traverse(root.left, root.right)
return root
