思想
二叉樹(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 889
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
輸入：
（1）preorder: List[int]州泊，前序遍歷整數(shù)數(shù)組
（2）postorder: List[int]丧蘸，后序遍歷整數(shù)數(shù)組
輸出：
TreeNode，根據(jù)兩個(gè)遍歷數(shù)組構(gòu)建一顆二叉樹(shù)遥皂，返回根節(jié)點(diǎn)力喷。
舉例：
給定 preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
返回二叉樹(shù) [1,2,3,4,5,6,7]
1
/ \
2 3
/ \ / \
4 5 6 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是最先遍歷當(dāng)前節(jié)點(diǎn)的陈症。
# 前序
root.val | root.left (left_root, ...) | root.right (right_root, ...)
# 后序
root.left (..., left_root) | root.right (..., right_root) | root.val
接著在前序當(dāng)前根節(jié)點(diǎn)的下一個(gè)位置獲得左子樹(shù)的根節(jié)點(diǎn)蔼水，接著在后序中尋找對(duì)應(yīng)元素的位置（題目中沒(méi)有重復(fù)的元素），這樣就發(fā)現(xiàn)了左右子樹(shù)的索引邊界录肯。
編碼
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_preorder_and_postorder_traversal(preorder: List[int], postorder: List[int]) -> Optional[
TreeNode]:
# 記錄后序的元素下標(biāo)
postorder_dict = {}
def build(preorder: List[int], prestart: int, preend: int, postorder: List[int], poststart: int, postend: int) -> Optional[TreeNode]:
# base 條件趴腋，返回樹(shù)子葉的左右
if prestart > preend:
return None
if prestart == preend:
return TreeNode(preorder[prestart])
# 獲取 root 和左右子樹(shù)范圍
root_val = preorder[prestart]
partition_index = postorder_dict[preorder[prestart + 1]]
size = partition_index - poststart + 1
# 構(gòu)建樹(shù)
root = TreeNode(root_val)
root.left = build(preorder, prestart + 1, prestart + size, postorder, poststart, partition_index)
root.right = build(preorder, prestart + size + 1, preend, postorder, partition_index + 1, postend - 1)
return root
# 獲取后序的元素下標(biāo)位置
for i in range(len(postorder)):
postorder_dict[postorder[i]] = i
return build(preorder, 0, len(preorder) - 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
二叉樹(shù) 15
