617.二叉搜索树的最小绝对差

文档讲解:代码随想录

题目链接：. - 力扣（LeetCode）

遇到二叉搜索树，就要知道这棵树在中序遍历的情况下是一个升序的遍历。

这道题目的难点就是如何使用双指针遍历二叉树，一个指向中序遍历的正在遍历的节点，一个指向中序遍历前一个结点

在中序遍历过程中，遍历到的节点是不断递增的，相当于有一个指针是不断移动的，我们只要让另一个指针指向现在指针指向的指针就可以

如何确定递归函数有无返回值：有返回值的情况：返回二叉树是否符合某一特性或者某一结点的数值，遍历某条特定的路径，或是找到某一结点，本题是需要遍历整个二叉树所以无返回值

class Solution:
    def __init__(self):
        self.result = float("inf")
        self.pre = None
    def traversal(self,root):
        if not root:
            return 
        self.traversal(root.left) #向左遍历
        #中
        if self.pre is not None: 
            self.result = min(self.result,root.val - self.pre.val)
        self.pre = root
        #右
        self.traversal(root.right)
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        self.traversal(root)
        return self.result

501.二叉搜索树中的众数

文档讲解：代码随想录

题目链接：. - 力扣（LeetCode）

涉及到二叉搜索树，遍历顺序一定是中序遍历，中序遍历的才是一个升序数组。然后将处理逻辑放在中间，和上一个题的结构是一样的，在向左遍历和向右遍历中间写上处理代码。

难点：众数可能有多个

所以我们要对每个不一样的元素都初始化一个count，比较哪个count最大，并且如果有跟count一样大的其他元素对应的count，那么这两个元素都是众数

代码技巧：①和上一题一样，也是使用双指针 ②定义两个频率变量，一个是当前遍历的元素的频率count，一个是所有的遍历过的元素的最高频率max_count  ③收获结果集：如果count和max_count 一样，就保存到结果集中 ④在遍历的过程中不断更新max_count,以及结果集

class Solution:
    

    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        ###定义全局变量
        pre = None
        count = 0
        max_count = 0
        result = []
        def traversal(root):
            nonlocal pre, count, max_count, result
            if not root:
                return 
            traversal(root.left)
            #统计当前节点的频率
            if pre == None:
                count = 1
            else:
                if pre.val == root.val:
                    count +=1
                else:
                    count = 1
            #比较当前节点的频率和最大频率
            if count > max_count:
                max_count = count
                result = [root.val] #重置
            ###下面这个条件不可以写为if，这个条件和上面的是互斥的，如果写为if那么上面那个执行完之后，max_count = count了，下面的if条件还是会执行
            elif  count == max_count:
                result.append(root.val)
            ##不要忘记更新pre的值
            pre = root
            traversal(root.right)
        traversal(root)
        return result

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

文档链接：代码随想录

题目链接：. - 力扣（LeetCode）

审题：

• 所有 Node.val 互不相同 。
• p != q
• p 和 q 均存在于给定的二叉树中。

如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。也就是我们要从下往上处理

 遍历是没有办法从下往上遍历的，但是处理顺序可以从下往上处理，后序遍历，左右中，便是从下往上处理。有递归就会有回溯，回溯的过程就会让我们从底往上去遍历

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root == None 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 left and right:
            return root
        if left and not right:
            return left
        elif not left and right:
            return right
        else:
            return None