Medium

题目描述

最大树是这样的一棵树：其中每个节点的值都大于其子树中任何其他值。

给你一个最大二叉树的根节点 root 和一个整数 val。

就像之前的问题一样，给定的树是从一个列表 a（root = Construct(a)）递归地使用下述 Construct(a) 例程构造的：

  • 如果 a 为空，返回 null
  • 否则，令 a[i] 是 a 的最大元素。创建一个值为 a[i] 的根节点
  • root 的左子树将被构造为 Construct([a[0], a[1], ..., a[i - 1]])
  • root 的右子树将被构造为 Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]])
  • 返回 root

注意，我们没有直接给出 a，只是给出一个根节点 root = Construct(a)。

假设 b 是 a 的副本，并在其末尾附加值 val。题目数据保证 b 中的值是唯一的。

返回 Construct(b)。

示例 1：

输入：root = [4,1,3,null,null,2], val = 5
输出：[5,4,null,1,3,null,null,2]
解释：a = [1,4,2,3], b = [1,4,2,3,5]

示例 2：

输入：root = [5,2,4,null,1], val = 3
输出：[5,2,4,null,1,null,3]
解释：a = [2,1,5,4], b = [2,1,5,4,3]

示例 3：

输入：root = [5,2,3,null,1], val = 4
输出：[5,2,4,null,1,3]
解释：a = [2,1,5,3], b = [2,1,5,3,4]

提示：

  • 树中节点数目在范围 [1, 100] 内
  • 1 <= Node.val <= 100
  • 树的所有值都是唯一的
  • 1 <= val <= 100

解题思路

这道题的关键在于理解最大二叉树的构造规则和新值插入后的变化。

由于新值 val 是追加到原数组 a 的末尾，我们需要分析插入位置的特点：

  1. 如果 val 大于根节点的值：由于 val 是数组中的最大值，它将成为新的根节点，原来的整棵树成为新根的左子树。

  2. 如果 val 小于根节点的值：val 只能影响右子树。根据最大二叉树的性质，我们需要在右子树中找到正确的插入位置。

具体算法：

  • 从根节点开始遍历
  • 如果当前节点值小于 val，说明 val 应该成为新的根，当前子树成为 val 的左子树
  • 如果当前节点值大于 val，继续向右子树递归
  • 如果右子树为空，直接将 val 作为右子节点

这个解法的巧妙之处在于利用了最大二叉树的构造特性：新元素总是添加到数组末尾，所以只会影响树的右侧结构。

代码实现

class Solution {
public:
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
        if (!root || val > root->val) {
            TreeNode* newRoot = new TreeNode(val);
            newRoot->left = root;
            return newRoot;
        }
        
        root->right = insertIntoMaxTree(root->right, val);
        return root;
    }
};

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

public class Solution {
    public TreeNode InsertIntoMaxTree(TreeNode root, int val) {
        if (root == null || val > root.val) {
            TreeNode newRoot = new TreeNode(val);
            newRoot.left = root;
            return newRoot;
        }
        
        root.right = InsertIntoMaxTree(root.right, val);
        return root;
    }
}

var insertIntoMaxTree = function(root, val) {
    if (!root || val > root.val) {
        const newRoot = new TreeNode(val);
        newRoot.left = root;
        return newRoot;
    }
    
    root.right = insertIntoMaxTree(root.right, val);
    return root;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)最坏情况下需要遍历到最右侧的叶子节点，n为树中节点数
空间复杂度O(h)递归调用栈的深度，h为树的高度

相关题目