思想
二叉樹的核心思想是分治和遞歸诅炉，特點(diǎn)是遍歷方式驻襟。
解題方式常見兩類思路：
- 遍歷一遍二叉樹尋找答案真友；
- 通過分治分解問題尋求答案叔锐；
遍歷分為前中后序挪鹏，本質(zhì)上是遍歷二叉樹過程中處理每個節(jié)點(diǎn)的三個特殊時間點(diǎn)：
- 前序是在剛剛進(jìn)入二叉樹節(jié)點(diǎn)時執(zhí)行；
- 后序是在將要離開二叉樹節(jié)點(diǎn)時執(zhí)行愉烙；
- 中序是左子樹遍歷完進(jìn)入右子樹前執(zhí)行讨盒；
# 前序
1 node
/ \
2 left 3 right
中左右
# 中序
2 node
/ \
1 left 3 right
左中右
# 后序
3 node
/ \
1 left 2 right
左右中
多叉樹只有前后序列遍歷，因為只有二叉樹有唯一一次中間節(jié)點(diǎn)的遍歷
題目的關(guān)鍵就是找到遍歷過程中的位置步责，插入對應(yīng)代碼邏輯實現(xiàn)場景的目的返顺。
實例
兩數(shù)之和IV - 輸入二叉搜索樹 leetcode 653
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
輸入：
（1）root: TreeNode，二叉樹的根節(jié)點(diǎn)蔓肯；
（2）k: int遂鹊，目標(biāo)兩數(shù)和；
輸出：
bool省核，返回樹中是否存在兩個元素之和為目標(biāo)值稿辙。
舉例：
給定二叉樹 [5,3,6,2,4,null,7], k = 9
5 + 4 = 9昆码，存在兩個元素和是 9气忠，返回 True
5
/ \
3 6
/ \ / \
2 4 7
二叉樹的數(shù)據(jù)存儲可以使用鏈表，也可以使用數(shù)組赋咽，往往數(shù)組更容易表達(dá)旧噪，根節(jié)點(diǎn)從 index=1 處開始存儲，浪費(fèi) index=0 的位置
left_child = 2 * parent
right_child = 2 * parent + 1
parent = child // 2
分治解
基本情境是獲得一個當(dāng)前節(jié)點(diǎn)和左右子樹脓匿，用一塊內(nèi)存記錄需要的元素淘钟，如果當(dāng)前節(jié)點(diǎn)值在需要的元素中，返回 True陪毡，否則繼續(xù)遍歷左右子樹米母，全部遍歷完不存在則返回 False勾扭。
base 條件是如果當(dāng)前節(jié)點(diǎn)為 None 則直接返回。
上例中铁瞒，目標(biāo)元素初始為 {}
- 從 5 開始遍歷妙色，需要 9-5 = 4，目標(biāo)元素更新為 {4}
- 左子樹 3慧耍，需要 9-3 = 6身辨，目標(biāo)元素更新為 {4,6}
- 左子樹 2，需要 9-2 = 7芍碧，目標(biāo)元素更新為 {4,6,7}
- 左子樹 None煌珊，返回
- 右子樹 4，屬于目標(biāo)元素泌豆，返回 True
編碼
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 two_sum_iv_input_is_a_bst(root: Optional[TreeNode], k: int) -> bool:
# 目標(biāo)元素集
target = set()
def traverse(root: TreeNode) -> bool:
# 初始條件定庵，空節(jié)點(diǎn)不處理
if root is None:
return
# 前序遍歷位置，比對當(dāng)前節(jié)點(diǎn)值并處理
nonlocal target
if root.val in target:
# 當(dāng)前節(jié)點(diǎn)值在目標(biāo)元素集中踪危，返回存在
return True
else:
# 當(dāng)前節(jié)點(diǎn)值不在目標(biāo)元素集中洗贰，將新的目標(biāo)加入
target.add(k - root.val)
# 左右子樹分別遍歷，都不存在則返回 False
return traverse(root.left) or traverse(root.right) or False
return traverse(root)
相關(guān)
二叉樹 0
二叉樹 1
二叉樹 2
二叉樹 3
二叉樹 4
二叉樹 5
二叉樹 6
二叉樹 7
二叉樹 8
二叉樹 9
二叉樹 10
二叉樹 11
