day21| 530+501+236

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. 递归需要多多练习和总结