思想
二叉樹(shù)的核心思想是分治和遞歸辰如，特點(diǎn)是遍歷方式怎栽。
解題方式常見(jiàn)兩類(lèi)思路：
- 遍歷一遍二叉樹(shù)尋找答案颊亮；
- 通過(guò)分治分解問(wèn)題尋求答案剔宪；
遍歷分為前中后序拂铡，本質(zhì)上是遍歷二叉樹(shù)過(guò)程中處理每個(gè)節(jié)點(diǎn)的三個(gè)特殊時(shí)間點(diǎn)：
- 前序是在剛剛進(jìn)入二叉樹(shù)節(jié)點(diǎn)時(shí)執(zhí)行；
- 后續(xù)是在將要離開(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í)例
二叉樹(shù)最大深度 leetcode 104
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
輸入：
root: TreeNode，二叉樹(shù)的根節(jié)點(diǎn)
輸出：
int骚秦，二叉樹(shù)的最大深度
舉例：
給定二叉樹(shù) [3,9,20,None,None,15,7]她倘，最大深度返回 3.
二叉樹(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
3
/ \
9 20
/ \
15 7
遍歷解
用一個(gè)變量記錄最大深度胞得，遍歷一遍樹(shù)，取得最大深度屹电。前序位置進(jìn)入新一層當(dāng)前深度 +1阶剑，后序位置返回上一層當(dāng)前深度 -1.
分治解
二叉樹(shù)的最大深度等于子樹(shù)的最大深度 +1
編碼
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 maximum_depth_of_binary_tree_traverse(root: Optional[TreeNode]) -> int:
# 全局變量初始化
cur_depth, max_depth = 0, 0
def traverse(root: TreeNode):
nonlocal cur_depth, max_depth
# 遞歸終止條件
if root is None:
return
# 前序位置進(jìn)入新一層
cur_depth += 1
max_depth = max(cur_depth, max_depth)
traverse(root.left)
traverse(root.right)
# 后序位置返回上一層
cur_depth -= 1
traverse(root)
return max_depth
def maximum_depth_of_binary_tree_recursive(root: Optional[TreeNode]) -> int:
# 遞歸終止條件跃巡，root 為 None，此時(shí)深度為 0
if root is None:
return 0
left_max_depth = maximum_depth_of_binary_tree_recursive(root.left)
right_max_depth = maximum_depth_of_binary_tree_recursive(root.right)
# 當(dāng)前最大深度是左右子樹(shù)最大深度較大值 +1
return max(left_max_depth, right_max_depth) + 1
