530. 二叉搜索樹的最小絕對差
題目
思路與解法
第一想法： 一個二叉搜索樹的最小絕對差，從根結點看，它的結點與它的最小差值一定出現在 左子樹的最右結點（左子樹最大值）和右子樹的最左結點（右子樹的最小值）。
這樣搞復雜了，直接層序遍歷，然后后值減前值，記錄最小值
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:def getMinimumDifference(self, root: Optional[TreeNode]) -> int:self.inorder_list = []self.inorder(root)res = float('inf')for i in range(len(self.inorder_list)-1):cur = self.inorder_list[i+1] - self.inorder_list[i]res = cur if cur < res else resreturn resdef inorder(self,root):if not root:returnself.inorder(root.left)self.inorder_list.append(root.val)self.inorder(root.right)
501.二叉搜索樹中的眾數
題目
思路與解法
第一想法： 遍歷
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:def findMode(self, root: Optional[TreeNode]) -> List[int]:from collections import defaultdictclass Solution:def searchBST(self, cur, freq_map):if cur is None:returnfreq_map[cur.val] += 1 # 統計元素頻率self.searchBST(cur.left, freq_map)self.searchBST(cur.right, freq_map)def findMode(self, root):freq_map = defaultdict(int) # key:元素，value:出現頻率result = []if root is None:return resultself.searchBST(root, freq_map)max_freq = max(freq_map.values())for key, freq in freq_map.items():if freq == max_freq:result.append(key)return result
236. 二叉樹的最近公共祖先
題目
思路與解法
carl的講解： 如果左右都有返回值，那就是它。不可能出現第二個左右都有返回值的節點，因為本題樹中節點不重復。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if root == p or root == q or root == None:return rootleft = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)if left and right:return rootif not left and right:return rightelif left and not right:return leftelse:return None
