思想
二叉樹的核心思想是分治和遞歸，特點(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)鍵就是找到遍歷過程中的位置，插入對應(yīng)代碼邏輯實(shí)現(xiàn)場景的目的。
實(shí)例
二叉樹的直徑 leetcode 543
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
輸入：
root: TreeNode，二叉樹的根節(jié)點(diǎn)
輸出：
int，返回二叉樹的直徑：任意兩個(gè)節(jié)點(diǎn)路徑長度中的最大值，或許穿過或許未穿過根節(jié)點(diǎn)。
舉例：
給定二叉樹 [9,None,1,2,3,4,5]，返回 3。最大直徑是 [4,2,1,3] 或者 [5,2,1,3] 或者 [4,2,1,9]
二叉樹的數(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
9
/ \
None 1
/ \
2 3
/ \
4 5
直徑是解題的關(guān)鍵，直徑是一個(gè)節(jié)點(diǎn)左右子樹的最大深度之和
遍歷解
遍歷每個(gè)節(jié)點(diǎn)，計(jì)算每個(gè)節(jié)點(diǎn)的左右子樹最大深度之和求當(dāng)前節(jié)點(diǎn)的直徑，將其中的最大值返回。
分治解
遍歷每個(gè)節(jié)點(diǎn)需要的時(shí)間很長，時(shí)間復(fù)雜度最壞情況下是 O(n^2)
分治的優(yōu)化方式是在后序遍歷的位置拿到最大深度做優(yōu)化。
編碼
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 diameter_of_binary_tree(root: Optional[TreeNode]) -> int:
max_diameter = 0
def max_depth(root: Optional[TreeNode]) -> int:
# base 條件，節(jié)點(diǎn)為 None 時(shí)計(jì)數(shù)為 0
if root is None:
return 0
left_max_depth = max_depth(root.left)
right_max_depth = max_depth(root.right)
return max(left_max_depth, right_max_depth) + 1
def traverse(root: Optional[TreeNode]):
if root is None:
return
left_max_depth = max_depth(root.left)
right_max_depth = max_depth(root.right)
diameter = left_max_depth + right_max_depth
nonlocal max_diameter
max_diameter = max(max_diameter, diameter)
traverse(root.left)
traverse(root.right)
traverse(root)
return max_diameter
def diameter_of_binary_tree_optimize(root: Optional[TreeNode]) -> int:
max_diameter = 0
def max_depth(root: Optional[TreeNode]):
if root is None:
return 0
left_max_depth = max_depth(root.left)
right_max_depth = max_depth(root.right)
# 后序位置獲取當(dāng)前子樹全量信息處理最大直徑
diameter = left_max_depth + right_max_depth
nonlocal max_diameter
max_diameter = max(max_diameter, diameter)
return max(left_max_depth, right_max_depth) + 1
max_depth(root)
return max_diameter
