目錄
1.?啥時候用二叉樹？
（1）典型問題
（2）核心思路
2.?BFS、DFS、BST
2.1 廣度優先搜索BFS
（1）適用任務
（2）解決思路??：使用隊列逐層遍歷
2.2?深度優先搜索DFS
（1）三種變體（前中后序）
（2）解決思路：遞歸實現
2.3?二叉搜索樹BST
3.?LeetCode
3.1 BFS
（1）199?二叉樹的右視圖
（2）1161?最大層內元素和
3.2?DFS
（1）104 二叉樹的最大深度
（2）872?葉子相似的樹
（3）1448?統計二叉樹中好節點的數目
（4）1372?二叉樹中的最長交錯路徑
（5）236?二叉樹的最近公共祖先
3.3?BST
（1）700?二叉搜索樹中的搜索
（2）450?刪除二叉搜索樹中的節點
（3）98?驗證二叉搜索樹
（4）230?二叉搜索樹中第k小的元素
1.?啥時候用二叉樹？
（1）典型問題
分層數據處理（文件系統、組織架構）
高效搜索（BST中查找/插入/刪除）
路徑問題（根節點到葉節點的路徑）
樹形結構操作（鏡像、深度、平衡性判斷）
表達式解析（語法樹）
（2）核心思路
def solve(root):if root is None: # 關鍵：始終先處理空節點return base_value # 如深度為0，路徑為空列表等# 遞歸分解子問題left_result = solve(root.left) # 處理左子樹right_result = solve(root.right) # 處理右子樹# 合并結果（根據問題類型選擇策略）return combine(root.val, left_result, right_result)2.?BFS、DFS、BST
2.1 廣度優先搜索BFS
（1）適用任務
-- 層序遍歷（按層級輸出節點）
-- 最短路徑（根節點到目標節點的最小深度）
-- 尋找最近鄰節點
（2）解決思路??：使用隊列逐層遍歷
from collections import dequedef bfs(root):if not root: return []queue = deque([root])result = []while queue:level = []for _ in range(len(queue)): # 遍歷當前層node = queue.popleft()level.append(node.val)if node.left: queue.append(node.left)if node.right: queue.append(node.right)result.append(level) # 保存當前層結果return result2.2?深度優先搜索DFS
（1）三種變體（前中后序）
| 遍歷方式?? | 應用場景 | ??解決任務?? | ??操作順序?? |
|---|---|---|---|
| ??前序遍歷?? | 節點初始化、路徑記錄、自頂向下操作 | 復制樹、表達式前綴表示 | 根 → 左 → 右 |
| ??中序遍歷?? | 二叉搜索樹操作、順序相關處理 | BST升序輸出、表達式解析 | 左 → 根 → 右 |
| ??后序遍歷?? | 子樹信息統計、依賴子樹結果的操作 | 子樹統計、內存釋放 | 左 → 右 → 根 |
關鍵判斷依據：??當前節點操作與子樹操作的關系?
如果操作依賴子樹結果 → 用后序遍歷（如：樹深度、子樹統計）
如果操作在前子樹操作前必須完成 → 用前序遍歷（如：路徑記錄、節點初始化）
如果涉及順序處理 → 用中序遍歷（如：BST中序遍歷有序）
（2）解決思路：遞歸實現
""" 前序遍歷 """
def preorder(root):if not root: returnprint(root.val) # 先操作根節點preorder(root.left)preorder(root.right)""" 中序遍歷 (BST關鍵) """
def inorder(root):if not root: returninorder(root.left)print(root.val) # 在中間操作節點inorder(root.right)""" 后序遍歷 """
def postorder(root):if not root: returnpostorder(root.left)postorder(root.right)print(root.val) # 最后操作根節點2.3?二叉搜索樹BST
左子樹節點值 <?根節點值 <?右子樹節點值
??（1）典型任務??
-- 查找元素（時間復雜度 ??O(log n)??）
-- 插入/刪除節點（保持BST性質）
-- 范圍查詢（如找出值在 [low, high] 間的節點）
（2）代碼模板
""" BST查找 """
def search(root, target):while root:if root.val == target: return Trueroot = root.left if target < root.val else root.rightreturn False""" BST插入（遞歸版）"""
def insert(root, val):if not root: return TreeNode(val)if val < root.val: root.left = insert(root.left, val)elif val > root.val: root.right = insert(root.right, val)return root # 返回更新后的子樹根節點""" 驗證BST（中序遍歷應用）"""
def isValidBST(root):stack, prev = [], float('-inf')while stack or root:while root: # 深入左子樹stack.append(root)root = root.leftroot = stack.pop()if root.val <= prev: return False # 破壞升序prev = root.valroot = root.right # 轉向右子樹return True3.?LeetCode
3.1 BFS
（1）199?二叉樹的右視圖
給定一個二叉樹的?根節點?root，想象自己站在它的右側，按照從頂部到底部的順序，返回從右側所能看到的節點值。
本質上就是二叉樹每一層的最后一個入隊的節點
from collections import deque
class Solution(object):def rightSideView(self, root):""":type root: Optional[TreeNode]:rtype: List[int]"""if not root: return []result=[]quene = deque([root])while quene:size=len(quene)for i in range(size):node = quene.popleft()if node.left: quene.append(node.left)if node.right:quene.append(node.right)cur_level_last = node.valresult.append(cur_level_last)return result（2）1161?最大層內元素和
給你一個二叉樹的根節點?root。設根節點位于二叉樹的第?1?層，而根節點的子節點位于第?2?層，依此類推。請返回層內元素之和最大的那幾層（可能只有一層）的層號，并返回其中最小的那個。
from collections import deque
class Solution(object):def maxLevelSum(self, root):""":type root: Optional[TreeNode]:rtype: int"""if not root: return 0quene = deque([root])level=1max_sum=[root.val, level]while quene:level_sum = 0level += 1for i in range(len(quene)):node = quene.popleft()level_sum += node.valif node.left: quene.append(node.left)if node.right:quene.append(node.right)if max_sum[0]<level_sum:max_sum = [level_sum, level-1]return max_sum[1]3.2?DFS
（1）104 二叉樹的最大深度
給定一個二叉樹?root?，返回其最大深度。二叉樹的?最大深度?是指從根節點到最遠葉子節點的最長路徑上的節點數。
DFS方法：后序遍歷，先看左右子樹的深度，更深的+1即為整棵樹的最大深度。
class Solution(object):def maxDepth(self, root):""":type root: Optional[TreeNode]:rtype: int"""if not root:return 0left_depth = self.maxDepth(root.left)right_depth = self.maxDepth(root.right)return max(left_depth,right_depth)+1BFS方法：
from collections import deque
class Solution(object):def maxDepth(self, root):""":type root: Optional[TreeNode]:rtype: int"""if not root:return 0quene = deque([root]) ## 隊列中存的是當前層的所有節點result = [] ## 用來保存每一層的節點while quene:cur_level = [] ## 當前層的節點level_size = len(quene) ## 當前層有幾個節點for i in range(level_size):node = quene.popleft() cur_level.append(node.val) ## 將當前節點加入當前層中if node.left: quene.append(node.left)if node.right: quene.append(node.right)result.append(cur_level)return len(result) （2）872?葉子相似的樹
如果有兩棵二叉樹的葉值序列是相同，那么我們就認為它們是?葉相似?的。如果給定的兩個根結點分別為?root1?和?root2?的樹是葉相似的，則返回?true；否則返回?false?。
DFS遍歷都是先左后右的，因此均能保證葉子節點的順序。
from collections import deque
class Solution(object):def find_leaves(self,root,leaves):if not root: return[]left_leaves = self.find_leaves(root.left,leaves)if not root.left and not root.right:leaves.append(root.val)right_leaves = self.find_leaves(root.right,leaves)return leavesdef leafSimilar(self, root1, root2):""":type root1: Optional[TreeNode]:type root2: Optional[TreeNode]:rtype: bool"""leaves1=[]leaves2=[]leaves1 = self.find_leaves(root1,leaves1)leaves2 = self.find_leaves(root2,leaves2)if leaves1==leaves2:return Trueelse:return False（3）1448?統計二叉樹中好節點的數目
給你一棵根為?root?的二叉樹，請你返回二叉樹中好節點的數目。「好節點」X 定義為：從根到該節點 X 所經過的節點中，沒有任何節點的值大于 X 的值。
采用前序遍歷（根 → 左 → 右）
根節點優先處理??：在訪問子節點前先判斷當前節點，符合路徑順序
及時更新最大值??：當遇到更大節點時，立即更新路徑最大值傳遞給子節點
class Solution(object):def dfs(self,root,cur_max):if not root: return 0count = 0if root.val>=cur_max:count=1cur_max = root.valcount += self.dfs(root.left,cur_max)count += self.dfs(root.right,cur_max)return countdef goodNodes(self, root):""":type root: Optional[TreeNode]:rtype: int"""cur_max=-10001return self.dfs(root,cur_max)（4）1372?二叉樹中的最長交錯路徑
給你一棵以?root?為根的二叉樹，二叉樹中的交錯路徑定義如下：
- 選擇二叉樹中?任意?節點和一個方向（左或者右）。
- 如果前進方向為右，那么移動到當前節點的的右子節點，否則移動到它的左子節點。
- 改變前進方向：左變右或者右變左。
- 重復第二步和第三步，直到你在樹中無法繼續移動。
交錯路徑的長度定義為：訪問過的節點數目 - 1（單個節點的路徑長度為 0 ）。請你返回給定樹中最長?交錯路徑?的長度。
使用后序遍歷：①當前節點的狀態計算??依賴子節點狀態??
②需要先知道子節點的?left_path 和?right_path 才能計算當前節點
class Solution(object):def longestZigZag(self, root):""":type root: Optional[TreeNode]:rtype: int""" self.max_path = 0def dfs(node):"""后序遍歷返回(left_path, right_path)""""""left_path: 從當前節點出發，第一步向左走能形成的最長交錯路徑長度""""""right_path: 從當前節點出發，第一步向右走能形成的最長交錯路徑長度"""if not node:return (0, 0)left_res = dfs(node.left) right_res = dfs(node.right)"""從當前節點向左走一步到左子節點（+1）然后需要向右走，查詢左子節點的??向右走狀態??(right_path，即left_res[1])"""left_path = 1 + left_res[1] if node.left else 0 """從當前節點向右走一步到右子節點（+1）然后需要向左走，查詢右子節點向左走的狀態(left_path，即right_res[0])"""right_path = 1 + right_res[0] if node.right else 0self.max_path = max(self.max_path, left_path, right_path)return (left_path, right_path)dfs(root)return self.max_path（5）236?二叉樹的最近公共祖先
祖先可能的情況：
（1）p 和 q 分屬不同子樹 → 當前根節點是 LCA
（2）p 和 q 在同一子樹 → LCA 在該子樹中
（3）p 或 q 自身就是 LCA（祖孫關系）
→?采用后序遍歷順序??（左右根）：
先深入子樹尋找節點，再處理當前節點判斷邏輯
class Solution(object):def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""if not root or root==p or root==q:return rootleft = self.lowestCommonAncestor(root.left,p,q) ## 在左子樹中找到的p或q（或LCA）right = self.lowestCommonAncestor(root.right,p,q) ## 在右子樹中找到的p或q（或LCA）if left and right: ## p和q分別在root的左右子樹中 return root ## root是它們最低層級的共同祖先if left: ## 兩個節點必定都在左子樹中## 此時left要么是p和q中的一個（如果尚未找到兩者關系），要么是p和q的LCA（如果已找到兩者關系）return left return right3.3?BST
（1）700?二叉搜索樹中的搜索
給定二叉搜索樹（BST）的根節點?root?和一個整數值?val。你需要在 BST 中找到節點值等于?val?的節點。 返回以該節點為根的子樹。 如果節點不存在，則返回?null?。
class Solution(object):def searchBST(self, root, val):""":type root: Optional[TreeNode]:type val: int:rtype: Optional[TreeNode]"""if not root: return nullwhile root:if root.val==val:return rootelif root.val<val:root=root.rightelse:root=root.left（2）450?刪除二叉搜索樹中的節點
要被刪除的節點存在三種情況：
1. 葉子節點??：直接刪除（返回None）
??2. 只有一個子節點??：用子節點替代當前節點
實現：直接返回子節點是讓父節點直接指向孫子節點
??3. 有兩個子節點??：找到前置節點（當前節點左子樹中最右側節點）替換
實現：用前置節點值覆蓋當前節點值?→ 刪除前置節點（遞歸調用）
class Solution(object):def deleteNode(self, root, key):""":type root: Optional[TreeNode]:type key: int:rtype: Optional[TreeNode]"""if not root: return Noneif key>root.val: ## key比當前節點大，在右子樹中刪root.right=self.deleteNode(root.right,key)elif key<root.val: ## key比當前節點小，在左子樹中刪root.left=self.deleteNode(root.left,key)else: ## 找到要刪的節點了，有以下4種情況""" 1.當前節點是葉子節點 → 直接刪除"""if not root.left and not root.right:return None""" 2.當前節點只有左孩子 → 直接用左孩子替代當前節點"""elif not root.right:return root.left""" 3.當前節點只有右孩子 → 直接用右孩子替代當前節點 """elif not root.left:return root.right""" 4. 當前節點左右孩子都有 → 用左子樹的最右側節點替代 """else:## 尋找前置節點pre = root.left while pre.right:pre=pre.right## 前置節點值賦給當前節點root.val = pre.val ## 刪除原前置節點 root.left = self.deleteNode(root.left,pre.val)return root（3）98?驗證二叉搜索樹
方案一：遞歸實現
每個節點都有值范圍約束：（low，high）
左子樹繼承上界：（low，node.val），右子樹繼承下界：（node.val，high）
class Solution(object):def isValidBST(self, root):""":type root: Optional[TreeNode]:rtype: bool"""def validate(node, low=float('-inf'), high=float('inf')):if not node:return Trueif node.val<=low or node.val>=high:return Falseis_left = validate(node.left, low, node.val)is_right = validate(node.right, node.val, high)return is_left and is_rightreturn validate(root)方案二：中序遍歷驗證
使用棧模擬中序遍歷過程，比較當前節點與前一個節點的值
class Solution(object):def isValidBST(self, root):stack=[]pre=Nonewhile stack or root:""" 左 """while root: stack.append(root)root=root.left""" 根 """root=stack.pop()if pre is not None and root.val<=pre: return False ## 當前值比pre值（其左側）小""" 右 """pre=root.valroot=root.rightreturn True（4）230?二叉搜索樹中第k小的元素
因為搜索樹的中序遍歷得到一個遞增序列，所以本質上就是求中序遍歷的第k個值。
class Solution(object):def kthSmallest(self, root, k):""":type root: Optional[TreeNode]:type k: int:rtype: int"""stack=[]count=0while root or stack:## 左while root:stack.append(root)root=root.left## 根root=stack.pop()count+=1if count==k: ## 是否是第k個 return root.val## 右root=root.right
_262)
