Day 20 二叉树：654. 最大, 617. 合并, 700. 搜索树搜索, 98. 验证搜索树

654. 最大二叉树

  • 思路
    • example
    • 递归，前序遍历
    • 空节点
      • 递归Base case包含空节点
      • 或 递归Base case不包含空节点：调用递归函数前需要加判断语句 if root.left:
    • 传递数组范围
  • 复杂度. 时间：O(n), 空间: O(n)
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        def traversal(nums, left, right): # left closed, right closed
            if left > right:
                return None
            val_max, idx_max = -float('inf'), -1
            for i in range(left, right+1):
                if nums[i] > val_max:
                    val_max = nums[i]
                    idx_max = i  
            node = TreeNode(val_max)
            node.left = traversal(nums, left, idx_max - 1)
            node.right = traversal(nums, idx_max + 1, right)
            return node  
        return traversal(nums, 0, len(nums)-1) 

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        n = len(nums)
        if n == 0:
            return None 
        max_ = -float('inf')
        idx = -1
        for i in range(n):
            if nums[i] > max_:
                max_ = nums[i]
                idx = i
        root = TreeNode(nums[idx])
        root.left = self.constructMaximumBinaryTree(nums[0:idx])
        root.right = self.constructMaximumBinaryTree(nums[idx+1:])
        return root

617. 合并二叉树

  • 思路
    • example
    • 把tree2合并到tree1上 (不需要额外构造树)
      • if tree1 == None: return tree2 (could be None)
      • if tree2 == None: return tree1
      • 否则root1.val += root2.val
    • 递归，前序遍历 （中序，后序亦可）
  • 复杂度. 时间：O(n), 空间: O(n)
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 == None:
            return root2 
        if root2 == None:
            return root1 
        root1.val += root2.val 
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right) 
        return root1 

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 == None:
            return root2 
        if root2 == None:
            return root1 
        root1.val += root2.val 
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right) 
        return root1
  • 迭代，层序，deque
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 == None: 
            return root2
        if root2 == None:
            return root1 
        que = collections.deque()
        que.append((root1, root2))
        while que:
            size = len(que)
            for _ in range(size):
                node1, node2 = que.popleft()
                node1.val += node2.val 
                if node1.left and node2.left: # 两个左节点都非空时才入队列
                    que.append((node1.left, node2.left))
                if node1.right and node2.right: # 两个右节点都非空时才入队列
                    que.append((node1.right, node2.right))
                if node1.left == None and node2.left:
                    node1.left = node2.left
                if node1.right == None and node2.right:
                    node1.right = node2.right 
                # 其它不需要处理
        return root1

700. 二叉搜索树中的搜索

  • 思路
    • example
    • 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
      你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
    • 递归
    • Base case：空节点或root.val == val
  • 复杂度. 时间：O(n), 空间: O(n)
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root == None:
            return None 
        if root.val == val:
            return root 
        elif root.val < val:
            return self.searchBST(root.right, val)
        else:
            return self.searchBST(root.left, val)
  • 迭代 (二分）
    • 二叉搜索树：有序。不需要利用栈或队列的帮助就可以实现迭代遍历。
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        while root:
            if root.val == val:
                return root 
            elif root.val < val:
                root = root.right 
            else:
                root = root.left 
        return None

98. 验证二叉搜索树

有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。

  • 思路
    • example
    • 递归
    • 注意搜索树的定义
      • 验证左右子树是否搜索树
      • 只比较root.val，root.left.val, root.right.val是不够的。下面的递归前序遍历是错误的。还需要验证根节点值小于右子树最小值，大于左子树最大值。
    • 上图中，就算右子树改为[6,3,7]也是False.
  • 复杂度. 时间：O(n), 空间: O(n)
# 错误代码
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def traversal(root):
            if root == None:
                return True
            if root.left and root.left.val >= root.val:
                return False
            if root.right and root.right.val <= root.val:
                return False
            return traversal(root.left) and traversal(root.right)
        return traversal(root)
  • 递归，中序遍历。BST利用中序遍历就是自然的递增顺序！
    • 中序遍历中，如果知道当前节点的pre节点，并且是递增顺序，那么符合要求。
    • 最简单的方法，中序遍历得到一个数组，再判断该数组是不是严格递增顺序。
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def traversal(root):
            nonlocal pre
            if root == None:
                return True  
            flag_left = traversal(root.left)
            if flag_left == False:
                return False
            if pre and root.val <= pre.val:
                return False 
            pre = root 
            flag_right = traversal(root.right) 
            if flag_right == False:
                return False 
            return True 
        pre = None     
        return traversal(root)

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def traversal(root):
            nonlocal pre 
            if root == None:
                return True 
            if traversal(root.left) == False:
                return False 
            if pre and pre.val >= root.val:
                return False 
            pre = root 
            if traversal(root.right) == False:
                return False 
            return True 
        pre = None 
        return traversal(root)
  • 迭代，中序遍历
    • cur + stack
    • 记录pre 节点或者pre节点的数值。
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        cur = root  
        stack = []
        pre_val = -float('inf')
        while cur or stack:
            if cur:
                stack.append(cur)
                cur = cur.left 
            else: 
                cur = stack.pop()
                if pre_val >= cur.val:
                    return False
                pre_val = cur.val  
                cur = cur.right 
        return True
  • 递归，前+后 序，递归函数参数
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def traversal(root, min_val, max_val):
            if root == None:
                return True 
            if root.val >= max_val or root.val <= min_val:
                return False  
            valid1 = traversal(root.left, min_val, root.val)
            valid2 = traversal(root.right, root.val, max_val)
            return valid1 and valid2  
        return traversal(root, -float('inf'), float('inf'))
  • 后序
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def traverse(root):
            if root == None:
                return True, float('inf'), -float('inf') # !!!
            if root.left == None and root.right == None:
                return True, root.val, root.val 
            valid_left, min_left, max_left = traverse(root.left)  
            if valid_left == False:
                return False, min_left, max_left  
            valid_right, min_right, max_right = traverse(root.right)  
            if valid_right == False:
                return False, min_right, max_right  
            if max_left < root.val < min_right:
                return True, min(min_left, min_right, root.val), max(max_left, max_right, root.val)  
            return False, min(min_left, min_right, root.val), max(max_left, max_right, root.val)  
        res, min_, max_ = traverse(root)  
        return res
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容