今日总结双指针法、二叉搜索树的中序遍历的有序性题目530.二叉搜索树的最小绝对差题目链接题目题解第一想法二叉搜索树两个节点间的最小差值一定会存在于中序遍历的相邻节点中间所以一边中序遍历一边更新pre和当前节点的最小差值。自己实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def getMinimumDifference(self, root: Optional[TreeNode]) - int: # 二叉搜索树两个节点间的最小差值一定会存在于中序遍历的相邻节点中间所以一边中序遍历一边更新pre和当前节点的最小差值 # 注意至少有两个节点从中序遍历第二个节点才开始计算(pre!cur) if not root or (not root.left and not root.right): return 0 pre None node root st[] min_difffloat(inf) while node or st: while node: st.append(node) nodenode.left nodest.pop() if pre: min_diff min(min_diff,node.val-pre.val) pre node node node.right return min_diff时间复杂度O(n)空间复杂度O(h)学习题解二叉搜索树的中序遍历是有序数组。迭代法中序遍历迭代也可以用if-else写法和统一迭代。if-else通过if cur每次只压一个节点然后立即转向左孩子。统一迭代压入None作为标记在栈中区分“待处理节点”和“已处理过子树的节点”。501.二叉搜索树中的众数题目链接题目题解第一想法中序遍历如果当前节点和pre节点相同更新数字频率。如果没有出现频率大于等于2的元素返回中序遍历数组。自己实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def findMode(self, root: Optional[TreeNode]) - List[int]: # 中序遍历如果当前节点和pre节点相同更新数字频率 if not root : return -float(inf) pre None node root st[] res [] traverse [] mp {} while node or st: while node: st.append(node) nodenode.left nodest.pop() if pre and pre.val node.val: if pre.val not in mp: mp[pre.val] 1 else: mp[pre.val] 1 traverse.append(node.val) pre node node node.right max_val -float(inf) for v in mp.values(): max_val max(max_val,v) for k,v in mp.items(): if v max_val: res.append(k) return res if res else traverse时间复杂度O(n)空间复杂度O(n)学习题解只遍历一遍的技巧用maxCount记录全局最大频率res存储答案。如果count maxCount将当前值加入res。如果count maxCount更新maxCount并清空res后加入当前值。解法1-递归中序实时更新序遍历二叉搜索树保证节点值非递减。用pre记录前一个节点count统计当前值连续出现的次数。空间复杂度 O(h)class Solution: def findMode(self, root: Optional[TreeNode]) - List[int]: self.pre None self.count 0 self.maxCount 0 self.res [] self.inorder(root) return self.res def inorder(self, node): if not node: return self.inorder(node.left) # 处理当前节点 if self.pre is None: self.count 1 elif self.pre.val node.val: self.count 1 else: self.count 1 self.pre node # 更新结果 if self.count self.maxCount: self.res.append(node.val) elif self.count self.maxCount: self.maxCount self.count self.res [node.val] self.inorder(node.right)解法2-迭代中序实时更新class Solution: def findMode(self, root: Optional[TreeNode]) - List[int]: if not root: return [] st [] cur root pre None count 0 maxCount 0 res [] while cur or st: while cur: st.append(cur) cur cur.left cur st.pop() # 处理当前节点 if pre is None: count 1 elif pre.val cur.val: count 1 else: count 1 pre cur if count maxCount: res.append(cur.val) elif count maxCount: maxCount count res [cur.val] cur cur.right return res236. 二叉树的最近公共祖先题目链接题目题解第一想法后序遍历时用字典记录每个节点子树中发现的 p/q/最近公共祖先当某节点左右子树均返回非空时该节点即为最近公共祖先。自己实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val x # self.left None # self.right None class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: if not root: return None st [root] # 存储每个节点子树中找到的 p/q 或 最近公共祖先 res {} while st: node st.pop() if node: # 后序入栈顺序根、右、左并在根后加 None 标记 st.append(node) st.append(None) if node.right: st.append(node.right) if node.left: st.append(node.left) else: # 遇到标记处理真实节点 node st.pop() if node is p or node is q: res[node] node # 当前节点就是目标 else: left res.get(node.left) right res.get(node.right) if left and right: return node # 左右子树各有一个当前为 LCA res[node] left or right # 向上传递非空结果 return res[root] # 根节点的结果即为 LCA当 p/q 有祖先关系时时间复杂度O(n)空间复杂度O(n)学习题解迭代法可以不用字典存储而是使用状态标记在栈中存储(node, visited)状态避免额外字典。在找到最近公共组先后可以立即退出循环避免遍历额外节点。可以用递归后序遍历空间复杂度O(h)# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val x # self.left None # self.right None class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: if not root: return None if root is p or root is q:return root left self.lowestCommonAncestor(root.left,p,q) right self.lowestCommonAncestor(root.right,p,q) if left and right:return root if left or right: return left or right else: return None今日收获二叉搜索树中序遍历相邻节点差值最小用 pre 指针一次遍历即可得到最小绝对差。众数问题可中序遍历时实时更新 count 和 maxCount无需额外字典空间 O(h)。普通二叉树的最近公共祖先后序递归若左右子树均返回非空则当前节点为 LCA若仅一侧非空则向上传递。学习时长2h。模板530. 二叉搜索树的最小绝对差中序迭代def getMinimumDifference(root): pre, cur None, root stack, min_diff [], float(inf) while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() if pre: min_diff min(min_diff, cur.val - pre.val) pre cur cur cur.right return min_diff501. 二叉搜索树中的众数中序递归 实时更新def findMode(root): res [] pre None count maxCount 0 def inorder(node): nonlocal pre, count, maxCount, res if not node: return inorder(node.left) # 处理当前节点 if not pre: count 1 elif pre.val node.val: count 1 else: count 1 pre node if count maxCount: res.append(node.val) elif count maxCount: maxCount count res [node.val] inorder(node.right) inorder(root) return res236. 二叉树的最近公共祖先后序递归def lowestCommonAncestor(root, p, q): if not root or root is p or root is q: return root left lowestCommonAncestor(root.left, p, q) right lowestCommonAncestor(root.right, p, q) if left and right: return root return left or right易错点530中序遍历时 pre 初始为 None第一个节点不计算差值注意树可能只有两个节点需正确处理。501实时更新 res 时当 count maxCount 必须清空 res 并重新加入当前值而不是 append。236递归终止条件遇到 p 或 q 立即返回无需继续向下。后序返回时若左右均非空则当前为 LCA若仅一侧非空则向上传递该侧结果。不要用值相等判断节点应使用is比较对象身份。