530. 二叉搜索树的最小绝对差
题目简述：
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
思路：
1. 二叉搜索树的中序遍历是单调的
2. 可以证明，求这单调数组中的最小绝对差，拿出来比较的两个数一定是相邻的
class Solution: def getMinimumDifference(self, root: Optional[TreeNode]) -> int: stack=[] minres=float('inf') pre=None while root or stack: if root: stack.append(root) root=root.left else: cur=stack.pop() if pre: minres=min(cur.val-pre.val,minres) pre=cur root=cur.right return minres
501. 二叉搜索树中得众数
题目简述：
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树
思路：
1. 一遍中序遍历一边记录每个数出现的次数，满足条件的加入数组当中
class Solution: def findMode(self, root: TreeNode) -> List[int]: stack = [] # 记录前一个元素值 pre = None # 记录次数 cnt = 0 # 记录最大次数 maxCnt = 0 # 记录结果 res = [] while root or stack: # 一直向左子树走，每一次将当前节点保存到栈中 if root: stack.append(root) root = root.left # 当前节点为空，证明走到了最左边，从栈中弹出节点 # 开始对右子树重复上述过程 else: cur = stack.pop() # 第一个节点 if pre == None: cnt = 1 # 如果与前一个节点的值相等 elif pre.val == cur.val: cnt += 1 else: cnt = 1 # 如果和最大次数相同，将值放入 res if cnt == maxCnt: res.append(cur.val) # 如果大于最大次数 if cnt > maxCnt: # 更新最大次数 maxCnt = cnt # 重新更新 res res = [cur.val] pre = cur root = cur.right return res
236. 二叉树的最近公共祖先
题目简述：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
思路：
1. 递归实现
2. 细致的分类讨论
class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: if not root or root.val == p.val or root.val == q.val: return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if not left and not right: return # 1. if not left: return right # 3. if not right: return left # 4. return root # 2. if left and right:
总结
1. 递归需要多多练习和总结