目錄
530.二叉搜索樹的最小絕對差
思路
代碼
501.二叉搜索樹中的眾數
思路
代碼
?236.?二叉樹的最近公共祖先??
思路
代碼
530.二叉搜索樹的最小絕對差
需要領悟一下二叉樹遍歷上雙指針操作，優先掌握遞歸?題目鏈接/文章講解：代碼隨想錄
視頻講解：二叉搜索樹中，需要掌握如何雙指針遍歷！| LeetCode：530.二叉搜索樹的最小絕對差_嗶哩嗶哩_bilibili
思路
? ? ? ? 二叉搜索樹的一個很重要的特性——中序遍歷是一個有序的遞增數組。有序遞增數組求兩個數的最小差值那不是有手就行。
代碼
class Solution:def __init__(self):self.vec = []def traversal(self, root):if root is None:returnself.traversal(root.left)self.vec.append(root.val) # 將二叉搜索樹轉換為有序數組self.traversal(root.right)def getMinimumDifference(self, root):self.vec = []self.traversal(root)if len(self.vec) < 2:return 0result = float('inf')for i in range(1, len(self.vec)):# 統計有序數組的最小差值result = min(result, self.vec[i] - self.vec[i - 1])return result501.二叉搜索樹中的眾數
和?530差不多雙指針思路，不過?這里涉及到一個很巧妙的代碼技巧。題目鏈接/文章講解：代碼隨想錄
代碼隨想錄視頻講解：不僅雙指針，還有代碼技巧可以驚艷到你！ | LeetCode：501.二叉搜索樹中的眾數_嗶哩嗶哩_bilibili
思路
? ? ? ?這里首次引入了pre指針，采用的還是二叉樹的中序遍歷，每次和前一個數進行比較，如果一樣，count就+1，每層遍歷時在遍歷中間節點后更新出現次數最大的數，注意每次更新最大的數需要把原來的res[ ] 清空，因為原來里面裝的不是出現頻率最大的數了。
代碼
from collections import defaultdict
from typing import Optional, Listclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def __init__(self):self.res = []self.count = 0self.maxcount = 0self.pre = Nonedef findMode(self, root: Optional[TreeNode]) -> List[int]:self.count = 0self.maxcount = 0self.pre = Noneself.res = []self.traversal(root)return self.resdef traversal(self, cur):if not cur:return None# 左self.traversal(cur.left)# 中if not self.pre:self.count = 1elif self.pre.val == cur.val:self.count += 1else:self.count = 1self.pre = curif self.count > self.maxcount: # 當前計數頻率大于最大值頻率，更新max，清空resself.maxcount = self.countself.res = []if self.count == self.maxcount:self.res.append(cur.val)# 右self.traversal(cur.right)return?236.?二叉樹的最近公共祖先??
本題其實是比較難的，可以先看我的視頻講解?題目鏈接：
代碼隨想錄
視頻講解：自底向上查找，有點難度！ | LeetCode：236. 二叉樹的最近公共祖先_嗶哩嗶哩_bilibili
思路
? ? ? ? 這種題就是我看著好像知道什么個原理，實際上讓我寫寫不了一點。。。（每日崩潰1/1）
?這道題使用的是后序遍歷，如果遍歷到當前節點就是p或者q就返回當前節點，層層往回傳，最后會傳到根節點。（因為是后序遍歷，哪怕找到了答案也要遍完的）（我知道我這么講大家根本聽不懂，所以點開視頻看吧，Carl哥講的超級nice，再配合代碼應該可以看懂）
代碼
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if root == p or root == q or root is None:return rootleft = self.lowestCommonAncestor(root.left,p,q)right = self.lowestCommonAncestor(root.right,p,q)if left is not None and right is not None:return rootelif left is None and right is not None :return rightelif left is not None and right is None:return leftelse:return None
)
