二叉搜索树的最小绝对差

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

class Solution:
    def __init__(self):
        self.result = float("inf")
        self.pre = None
    def dfs(self,cur):
        if cur is None:
            return 
        self.dfs(cur.left)
        if self.pre is not None:
            self.result = min(self.result,cur.val-self.pre.val)
        self.pre = cur
        self.dfs(cur.right)
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        self.dfs(root)
        return self.result

采用递归（中序遍历）加双指针的方法，遍历二叉搜索树，记录前一个节点，每次遍历到当前节点时，计算当前节点和前一个节点的差值，取最小值即可。

二叉搜索树中的众数

501. 二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按任意顺序返回。
假定 BST 满足如下定义：
结点左子树中所含节点的值小于等于当前节点的值
结点右子树中所含节点的值大于等于当前节点的值
左子树和右子树都是二叉搜索树

递归（中序遍历）+ 哈希表 + 双指针

class Solution:
    def __init__(self):
        self.count = 1
        self.pre = None
        self.result = {} 
        return 
    def dfs(self,cur):
        if cur is None:
            return 
        self.dfs(cur.left)
        if self.pre is not None:
            if self.pre.val == cur.val:
                self.count += 1
            else:
                self.count = 1
        self.result[cur.val] = self.count
        self.pre = cur
        self.dfs(cur.right)
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        self.dfs(root)
        target_count = max(self.result.values())
        num = [k for k,v in self.result.items() if v == target_count]
        return num

这是我没看视频前做的，额，最开始我想的是，相等就count+1，然后用flag来区分到底是哪个节点重复，额，然后写着写着就成了哈希表，然后感觉flag用cur.val替代更好

双指针+数组+递归（中序遍历）

class Solution:
    def __init__(self):
        self.Maxc = 0
        self.count = 1
        self.pre = None
        self.result = []
        return 
    def dfs(self,cur):
        if cur is None:
            return 
        self.dfs(cur.left)
        if self.pre is None:
            self.count = 1
        elif self.pre.val == cur.val:
            self.count += 1
        else:
            self.count = 1
        self.pre = cur
        if self.count ==self. Maxc:
            self.result.append(cur.val)
        if self.count > self.Maxc:
            self.Maxc = self.count
            self.result = [cur.val]
        self.dfs(cur.right)
        return 
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        self.dfs(root)
        return self.result

二叉树的最近公共祖先

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root == q or root ==p or root == None:
            return root
        left_ = self.lowestCommonAncestor(root.left,p,q)
        right_ = self.lowestCommonAncestor(root.right,p,q)
        if left_ and right_:
            return root
        elif left_ and not right_:
            return left_
        elif not left_ and right_:
            return right_
        else:
            return None