思想
二叉樹(shù)的核心思想是分治和遞歸，特點(diǎn)是遍歷方式是钥。
解題方式常見(jiàn)兩類思路：
- 遍歷一遍二叉樹(shù)尋找答案掠归；
- 通過(guò)分治分解問(wèn)題尋求答案；
遍歷分為前中后序悄泥，本質(zhì)上是遍歷二叉樹(shù)過(guò)程中處理每個(gè)節(jié)點(diǎn)的三個(gè)特殊時(shí)間點(diǎn)：
- 前序是在剛剛進(jìn)入二叉樹(shù)節(jié)點(diǎn)時(shí)執(zhí)行虏冻；
- 后序是在將要離開(kāi)二叉樹(shù)節(jié)點(diǎn)時(shí)執(zhí)行；
- 中序是左子樹(shù)遍歷完進(jìn)入右子樹(shù)前執(zhí)行弹囚；
# 前序
1 node
/ \
2 left 3 right
中左右
# 中序
2 node
/ \
1 left 3 right
左中右
# 后序
3 node
/ \
1 left 2 right
左右中
多叉樹(shù)只有前后序列遍歷厨相，因?yàn)橹挥卸鏄?shù)有唯一一次中間節(jié)點(diǎn)的遍歷
題目的關(guān)鍵就是找到遍歷過(guò)程中的位置，插入對(duì)應(yīng)代碼邏輯實(shí)現(xiàn)場(chǎng)景的目的鸥鹉。
實(shí)例
從中序與后序遍歷序列構(gòu)造二叉樹(shù) leetcode 106
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
輸入：
（1）inorder: List[int]蛮穿，中序遍歷整數(shù)數(shù)組
（2）postorder: List[int]，后序遍歷整數(shù)數(shù)組
輸出：
TreeNode毁渗，根據(jù)兩個(gè)遍歷數(shù)組構(gòu)建一顆二叉樹(shù)践磅，返回根節(jié)點(diǎn)。
舉例：
給定 inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
返回二叉樹(shù) [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
二叉樹(shù)的數(shù)據(jù)存儲(chǔ)可以使用鏈表灸异，也可以使用數(shù)組音诈，往往數(shù)組更容易表達(dá)，根節(jié)點(diǎn)從 index=1 處開(kāi)始存儲(chǔ)绎狭，浪費(fèi) index=0 的位置
left_child = 2 * parent
right_child = 2 * parent + 1
parent = child // 2
分治解
基本情境是找到當(dāng)前構(gòu)建二叉樹(shù)的根節(jié)點(diǎn)和左右子樹(shù)细溅，要利用中序和后序遍歷的特點(diǎn)。
根節(jié)點(diǎn)很容易獲得儡嘶，就是后序遍歷當(dāng)前范圍的最后一個(gè)元素喇聊，因?yàn)楹笮虮闅v是最后進(jìn)入當(dāng)前節(jié)點(diǎn)的。
# 中序
root.left ... | root.val | root.right ...
# 后序
root.left ... | root.right ... | root.val
通過(guò)后序的根節(jié)點(diǎn)蹦狂，能夠在中序的數(shù)組中找到誓篱，進(jìn)而獲取左子樹(shù)和右子樹(shù)朋贬。
題目中說(shuō)明沒(méi)有重復(fù)元素，因此可以用哈希存儲(chǔ)元素的下標(biāo)提高效率窜骄。
編碼
from typing import Optional, List
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def construct_binary_tree_from_inorder_and_postorder_traversal(inorder: List[int], postorder: List[int]) -> Optional[
TreeNode]:
# 記錄中序的元素下標(biāo)
inorder_dict = {}
def build(inorder: List[int], instart: int, inend: int, postorder: List[int], poststart: int, postend: int) -> Optional[TreeNode]:
# base 條件锦募，返回樹(shù)子葉的左右 None
if instart > inend:
return None
# 獲取 root 和左右子樹(shù)范圍
root_val = postorder[postend]
partition_index = inorder_dict[root_val]
size = partition_index - instart
# 構(gòu)建樹(shù)
root = TreeNode(root_val)
root.left = build(inorder, instart, partition_index - 1, postorder, poststart, poststart + size - 1)
root.right = build(inorder, partition_index + 1, inend, postorder, poststart + size, postend - 1)
return root
# 獲取中序的元素下標(biāo)位置
for i in range(len(inorder)):
inorder_dict[inorder[i]] = i
return build(inorder, 0, len(inorder) - 1, postorder, 0, len(postorder) - 1)
相關(guān)
二叉樹(shù) 0
二叉樹(shù) 1
二叉樹(shù) 2
二叉樹(shù) 3
二叉樹(shù) 4
二叉樹(shù) 5
二叉樹(shù) 6
二叉樹(shù) 7
二叉樹(shù) 8
二叉樹(shù) 9
二叉樹(shù) 10
二叉樹(shù) 11
二叉樹(shù) 12
二叉樹(shù) 13
二叉樹(shù) 14
