『LeetCode』998 最大二叉树 II

题目

998. 最大二叉树 II

最大树 定义：一棵树，并满足：其中每个节点的值都大于其子树中的任何其他值。

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

就像之前的问题那样，给定的树是利用 Construct(a) 例程从列表 a（root = Construct(a)）递归地构建的：

如果 a 为空，返回 null 。
否则，令 a[i] 作为 a 的最大元素。创建一个值为 a[i] 的根节点 root 。
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

相似题目

最大二叉树 (中等)

题解

【最大二叉树 II】简单模拟递归&非递归

模拟&递归

建议先看看之前的问题(题解) 再看这题比较容易理解。

之前的问题是通过数组构建二叉树，而这题是给出之前的问题中已经构建好的树，然后在数组末尾再插入一个值，现在要我们将新加入的值插入到已有的二叉树中。

其实分情况讨论一下即可：

若根节点为空，那么直接构建一个 TreeNode 并返回即可
若给定的 val 比根节点的值大，那么插入的值就是新的根节点，而新插入的值是在原数组最右边的，所以原来的 root 就是新的 root 的左子树
若不是前面两种情况，我们只需递归的在右子树中插入即可（同样是因为新插入的值是在原数组最右边所以是右子树）

# Code language: Python
class Solution:
    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return TreeNode(val)
        if root.val < val:
            return TreeNode(val, root, None)
        root.right = self.insertIntoMaxTree(root.right, val)
        return root

// Code language: Java
class Solution {
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        if (root.val < val) return new TreeNode(val, root, null);
        root.right = insertIntoMaxTree(root.right, val);
        return root;
    }
}

// Code language: C++
class Solution {
public:
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
        if (root == nullptr) return new TreeNode(val);
        if (root->val < val) return new TreeNode(val, root, nullptr);
        root->right = insertIntoMaxTree(root->right, val);
        return root;
    }
};

// Code language: JavaScript
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoMaxTree = function(root, val) {
    if (root == undefined) return new TreeNode(val);
    if (root.val < val) return new TreeNode(val, root, undefined);
    root.right = insertIntoMaxTree(root.right, val);
    return root;
};

时间复杂度: \(O(n)\)
空间复杂度: \(O(n)\)

非递归

其实理解了题目的话非递归实现也很简单，我们从根节点向右子树一路查找下去找到第一个比 val 小的结点用新建的结点取代其位置而原结点是新结点的右子树

讲得有点绕，但代码还是很好理解的

PS：设置一个哑结点就不用单独处理 val 比 root.val 还大以及 root 为空结点的情况啦~

# Code language: Python
class Solution:
    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        dummy = TreeNode(999, None, root)
        p = dummy
        while p.right and p.right.val > val:
            p = p.right
        p.right = TreeNode(val, p.right, None)
        return dummy.right

// Code language: Java
class Solution {
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        TreeNode dummy = new TreeNode(999, null, root), p = dummy;
        while (p.right != null && p.right.val > val) p = p.right;
        p.right = new TreeNode(val, p.right, null);
        return dummy.right;
    }
}

// Code language: C++
class Solution {
public:
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
        TreeNode* dummy = new TreeNode(999, nullptr, root);
        TreeNode* p = dummy;
        while (p->right != nullptr && p->right->val > val) p = p->right;
        p->right = new TreeNode(val, p->right, nullptr);
        p = dummy->right; delete dummy;
        return p;
    }
};

// Code language: JavaScript
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoMaxTree = function(root, val) {
    let dummy = new TreeNode(999, undefined, root), p = dummy;
    while (p.right != undefined && p.right.val > val) p = p.right;
    p.right = new TreeNode(val, p.right, undefined);
    return dummy.right;
};

时间复杂度: \(O(n)\)
空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』998 最大二叉树 II

题目

标签

相似题目

题解

模拟&递归

非递归