【LeetCode 刷题】二叉树-二叉搜索树的属性

此博客为《代码随想录》二叉树章节的学习笔记，主要内容为二叉搜索树的属性相关的题目解析。

文章目录

• 700.二叉搜索树中的搜索
• 98.验证二叉搜索树
• 530.二叉搜索树的最小绝对差
• 501.二叉搜索树中的众数
• 538.把二叉搜索树转换为累加树

700.二叉搜索树中的搜索

题目链接

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root or root.val == val:
            return root
        if root.val < val:
            return self.searchBST(root.right, val)
        else:
            return self.searchBST(root.left, val)

• 二叉树上的二分查找

98.验证二叉搜索树

题目链接

class Solution:
    pre = -inf
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        left = self.isValidBST(root.left)
        if not left or root.val <= self.pre:
            return False
        self.pre = root.val
        return self.isValidBST(root.right)

• 二叉搜索树的中序遍历结果是递增序列，因此在中序遍历过程中判断 pre.val 和 cur.val 的大小关系
• 上述写法中，由于只返回是否合法的布尔值，因此可以不用额外创建递归函数，将 pre 定义为类的成员变量
• pre 初始化为负无穷，可以避免特判

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

题目链接

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        pre, res = -inf, inf

        def traversal(node: Optional[TreeNode]) -> None:
            if not node:
                return
            traversal(node.left)
            nonlocal pre, res
            res = min(res, node.val - pre)
            pre = node.val
            traversal(node.right)
        
        traversal(root)
        return res

• 由于需要完整遍历整个二叉搜索树后，才可知最小绝对差，因此需要创建额外的递归函数，但函数返回值为空，仅用于遍历

501.二叉搜索树中的众数

题目链接

class Solution:
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        pre, cur, cur_max, res = -inf, -inf, -inf, []

        def traversal(node: Optional[TreeNode]) -> None:
            if not node:
                return
            traversal(node.left)
            nonlocal pre, cur, cur_max, res
            # 更新 cur
            cur = cur + 1 if node.val == pre else 1
            # 更新 cur_max 和 res
            if cur > cur_max:
                cur_max = cur
                res = [node.val]
            elif cur == cur_max:
                res.append(node.val)
            # 更新 pre
            pre = node.val
            traversal(node.right)
        
        traversal(root)
        return res

• 主要思路与上题类似，在中序遍历的同时统计特定的量
• 需要注意此题的众数可能不止一个，需要同时返回，因此当频次相同时，都放入 res 列表中作为答案

538.把二叉搜索树转换为累加树

题目链接

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        pre_sum = 0

        def traversal(node: Optional[TreeNode]) -> None:
            if not node:
                return
            traversal(node.right)
            nonlocal pre_sum
            pre_sum += node.val
            node.val = pre_sum
            traversal(node.left)
        
        traversal(root)
        return root

• 以"右、中、左"的顺序遍历，同时累加 pre_sum