【LeetCode 刷题】二叉树-修改与构造

此博客为《代码随想录》二叉树章节的学习笔记，主要内容为二叉树的修改与构造相关的题目解析。

文章目录

• 226. 翻转二叉树
• 105.从前序与中序遍历序列构造二叉树
• 106.从中序与后序遍历序列构造二叉树
• 654.最大二叉树
• 617.合并二叉树

226. 翻转二叉树

题目链接

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.right = left
        root.left = right
        return root

• 上述代码为后序遍历版本，即先递归处理左、右节点，之后处理中间节点
• 前序遍历也可正确求解，但中序遍历不可正确求解

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

题目链接

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return None
        left_size = inorder.index(preorder[0])
        left = self.buildTree(preorder[1:1+left_size], inorder[:left_size])
        right = self.buildTree(preorder[1+left_size:], inorder[left_size+1:])
        return TreeNode(preorder[0], left, right)

• list.index(x) 返回查找对象的索引位置，如果没有找到对象则抛出异常。因此此种构造方法只能处理节点值不重复的二叉树
• 优化点：
  • 用哈希表预处理 inorder 每个元素的下标，可以 O(1) 查到preorder[0] 在 inorder 的位置，从而 O(1) 知道左子树的大小
  • 把递归参数改成子数组下标区间（左闭右开区间）的左右端点，从而避免复制数组

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

题目链接

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not inorder:
            return None
        left_size = inorder.index(postorder[-1])
        left = self.buildTree(inorder[:left_size], postorder[:left_size])
        right = self.buildTree(inorder[left_size+1:], postorder[left_size:-1])
        return TreeNode(postorder[-1], left, right)

• 与上题类似，注意左右子树区间范围

654.最大二叉树

题目链接

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        left_size = nums.index(max(nums))
        left = self.constructMaximumBinaryTree(nums[0:left_size])
        right = self.constructMaximumBinaryTree(nums[left_size+1:])
        return TreeNode(max(nums), left, right)

617.合并二叉树

题目链接

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1:
            return root2
        if not root2:
            return root1
        left = self.mergeTrees(root1.left, root2.left)
        right = self.mergeTrees(root1.right, root2.right)
        return TreeNode(root1.val + root2.val, left, right)