【基础算法精讲-学习记录】二叉树3

视频学习记录

https://www.bilibili.com/video/BV14G411P7C1/

• 这一节的重点在于理解遍历二叉搜索树的三种方式，前序中序和后序，具体都在下面第一个代码记录中。

例题和课后作业代码记录

98. 验证二叉搜索树

https://leetcode.cn/problems/validate-binary-search-tree/description/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode], left=-inf, right=inf) -> bool:
        # 时间：遍历一遍树 On
        # 空间：最坏要递归n次，On
        # 后序遍历，先遍历完再从下往上判断
        def dfs(root):
            if not root:
                return inf, -inf 
            l_min, l_max = dfs(root.left) # lmax rmin用于判断当前节点是否合法
            if l_max >= root.val:
                return -inf, inf
            r_min, r_max = dfs(root.right)
            if r_min <= root.val:
                return -inf, inf 
            # lmin rmax用于返回当前节点为根的子树的数值范围
            return min(l_min, root.val), max(r_max, root.val)
        return dfs(root)[1] != inf


        # 中序遍历，先遍历左边，判断，再遍历右边
        pre = -inf # 总是当前节点的左子树
        def dfs(root):
            if not root:
                return True 
            l = dfs(root.left)
            if not l:
                return False
            nonlocal pre
            if pre >= root.val:
                return False 
            pre = root.val
            return dfs(root.right)
            
        return dfs(root)

        # 前序遍历，先判断，再递归
        if not root:
            return True
        x = root.val # 自顶向下由left和right规定当前节点的合法范围
        return left < x < right and self.isValidBST(root.left, left, x) and self.isValidBST(root.right, x, right)

700. 二叉搜索树中的搜索

https://leetcode.cn/problems/search-in-a-binary-search-tree/description/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        # 时间：遍历一遍树 On
        # 空间：最坏要递归n次，On
        if not root:
            return None 
        if root.val == val:
            return root 
        if root.val > val:
            return self.searchBST(root.left, val)
        else:
            return self.searchBST(root.right, val)

938. 二叉搜索树的范围和

https://leetcode.cn/problems/range-sum-of-bst/description/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        # 时间：遍历一遍树 On
        # 空间：最坏要递归n次，On
        ans = 0
        def dfs(root):
            if not root:
                return 
            if low <= root.val <= high:
                nonlocal ans 
                ans += root.val 
                dfs(root.left)
                dfs(root.right)
            elif root.val < low: 
                dfs(root.right)
            else:
                dfs(root.left)
        dfs(root)

        return ans

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

https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        # 时间：遍历一遍树 On
        # 空间：最坏要递归n次，On
        # 利用了中序遍历是有序的特点，直接比较上个点与当前点，就相当于整个树排升序后两两比较
        pre = -1e6
        ans = 1e7 
        def dfs(root):
            if not root:
                return 
            dfs(root.left)
            nonlocal ans, pre 
            ans = min(ans, abs(pre-root.val))
            pre = root.val 
            dfs(root.right)

        dfs(root)
        return ans

2476. 二叉搜索树最近节点查询

https://leetcode.cn/problems/closest-nodes-queries-in-a-binary-search-tree/description/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
        # 时间：对于m个queries，每个都要从树上往下找，Omlogn
        # 空间：最坏要递归n次，On
        # 利用中序遍历构建有序数组，然后二分查找，稳定logn找到一对最近节点
        ans = []
        nums = []

        def dfs(root):
            if not root:
                return 
            dfs(root.left)
            nums.append(root.val)
            dfs(root.right)
        dfs(root)
        for q in queries:
            index = bisect_left(nums, q)
            if index == len(nums):
                ans.append([nums[-1], -1])
                continue
            if index == 0 and q < nums[index]:
                ans.append([-1, nums[0]])
                continue
            if nums[index] == q:
                ans.append([q, q])
            else:
                ans.append([nums[index-1], nums[index]])
        
        return ans

        # 下面错误做法尝试利用二叉搜索树的结构来实现，但是忽略了每次查询最坏情况退化成On，还是纯粹二分稳
        ans = []
        def find_q(root):
            if not root:
                return 
            
            nonlocal left_max, right_min
            if root.val == q:
                left_max, right_min = q, q 
            elif root.val > q:
                right_min = min(right_min, root.val) if right_min != -1 else root.val 
                find_q(root.left)
            else:
                left_max = max(left_max, root.val) if left_max != -1 else root.val 
                find_q(root.right)

        for q in queries:
            left_max, right_min = -1, -1 
            find_q(root)
            ans.append([left_max, right_min])
        return ans
            

501. 二叉搜索树中的众数

https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        # 时间：遍历一遍树 On
        # 空间：最坏要递归n次，On，如果排除递归空间，O1
        # 利用中序遍历相当于有序遍历，相当于记录连续相同数字最大数量
        ans = []
        pre_val = -1 
        max_cnt = 0 
        cur_cnt = 0
        
        def dfs(root):
            if not root:
                return 
            dfs(root.left)
            nonlocal pre_val, max_cnt, cur_cnt 
            x = root.val 
            if x != pre_val: # 与上个节点值不同，就要重新计数
                cur_cnt = 0 
                pre_val = x
            cur_cnt += 1

            if cur_cnt > max_cnt:
                max_cnt = cur_cnt
                ans.clear()
                ans.append(x)
            elif cur_cnt == max_cnt:
                ans.append(x)
            
            dfs(root.right)
        dfs(root)
        return ans
        

230. 二叉搜索树中第 K 小的元素

https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        # 时间：遍历部分树 Ok
        # 空间：最坏要递归k次，Ok
        # 利用中序遍历，找到第k个算值的
        ans = 0
        index = 0
        def dfs(root):
            if not root:
                return 
            dfs(root.left)
            # print(root.val)
            nonlocal index 
            if index <= k: # 之所以还要=，是因为返回上面的时候也+1，使得上面的不能够覆盖ans
                index += 1
            if index == k:
                nonlocal ans 
                ans = root.val
                return
            dfs(root.right)
        dfs(root)
        return ans

1373. 二叉搜索子树的最大键值和

https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/description/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        # 时间：On 遍历了整棵树
        # 空间：递归空间最坏情况下On
        ans = -inf 

        def dfs(root):
            if not root:
                return inf, -inf, 0, True
            
            left_min, left_max, left_sum, left_valid = dfs(root.left)
            right_min, right_max, right_sum, right_valid = dfs(root.right)
            if not (left_valid and right_valid):
                return 0, 0, 0, False 

            x = root.val
            if x <= left_max or x >= right_min:
                return 0, 0, 0, False

            cur_sum = left_sum + x + right_sum
            nonlocal ans 
            ans = max(ans, cur_sum)
            return min(left_min, right_min, x), max(left_max, right_max, x), cur_sum, True

        dfs(root)
        return max(ans, 0) # 所有节点键值都为负数时，和最大的二叉搜索树为空。

105. 从前序与中序遍历序列构造二叉树

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # 时间：On，遍历一遍树
        # 空间：最坏情况下，隐性On递归空间
        # 前序遍历第一个是中点，利用中序遍历中点左边都是左子树，右边都是右子树
        if not preorder or not inorder:
            return None
        x = preorder[0]
        mid = inorder.index(x)
        return TreeNode(x, self.buildTree(preorder[1:mid+1], inorder[:mid]), self.buildTree(preorder[mid+1:], inorder[mid+1:]))
        

106. 从中序与后序遍历序列构造二叉树

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # 时间：On，遍历一遍树
        # 空间：最坏情况下，隐性On递归空间
        # 后序遍历最后一个是中点，利用中序遍历中点左边都是左子树，右边都是右子树
        if not postorder or not inorder:
            return None
        x = postorder[-1]
        # print(x, inorder, postorder)
        mid = inorder.index(x)
        return TreeNode(x, self.buildTree(inorder[:mid], postorder[:mid]), self.buildTree(inorder[mid+1:], postorder[mid:-1]))

889. 根据前序和后序遍历构造二叉树

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/description/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # 时间：On，遍历一遍树
        # 空间：最坏情况下，隐性On递归空间
        # 前序遍历第一个是中点，后序遍历最后一个也是中点
        # 没有中序，无法确定中点的左右子树顺序，但是可以规定，前序的第二个就是左子树的
        # 本题也硬性规定无重复值
        if not preorder:
            return None 
        if len(preorder) == 1:
            return TreeNode(preorder[0])
        left_head = preorder[1]
        left_size = postorder.index(left_head)+1 
        return TreeNode(preorder[0], self.constructFromPrePost(preorder[1:left_size+1], postorder[:left_size]), self.constructFromPrePost(preorder[left_size+1:], postorder[left_size:-1]))

1110. 删点成林

https://leetcode.cn/problems/delete-nodes-and-return-forest/description/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
        # 时间：On，遍历一遍树
        # 空间：最坏情况下，隐性On递归空间
        # 由于底下删完了不影响上面删，所以适合后序遍历
        ans = []
        delete_set = set(to_delete)
        def dfs(root):
            if not root:
                return None 
            root.left = dfs(root.left)
            root.right = dfs(root.right)
            x = root.val 
            if x in delete_set:
                if root.left:   
                    ans.append(root.left)
                if root.right:
                    ans.append(root.right)
                return None 
            else:
                return root
        root = dfs(root)
        if root:
            ans.append(root)
        return ans