关于后端:998-最大二叉树-II-常规模拟题

这是 LeetCode 上的 998. 最大二叉树 II，难度为中等。

Tag :「迭代」、「模仿」

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

给你最大树的根节点 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$

题意不是很好了解，先略微解释一下吧。

大略意思是最大树 root 是依据特定的规定结构进去的，即给定的 root 其实对应一个具体的 nums，题目要求是将 val 追加到 nums 的尾部，而后再对失去的 nums 使用雷同规定的结构，返回从新结构的最大树头结点。

依据结构规定，若有下标 $i < j$，则 $nums[i]$ 必然在 $nums[j]$ 水平线的右边，而 val 又是追加在原有 nums 的结尾。因而其最终地位分如下两种状况：

val 为新 nums 中的最大值，同时 val 又是追加在原有 nums 的结尾，此时将原有的 root 挂在 val 对应节点的左子树即可，新树的根节点为 val 对应节点；
否则，咱们只须要一直在 root 的右子树中找指标地位（反证法能够知，val 必不可能呈现在任一非右地位，否则可推断出在 val 左边仍有元素，这与 val 位于 nums 的结尾地位抵触）。假如指标地位的父节点为 prev，指标地位的原节点为 cur，依据结构规定可知 prev.right = node 且 node.left = cur，新树的根节点不变。

Java 代码：

class Solution {public TreeNode insertIntoMaxTree(TreeNode root, int val) {TreeNode node = new TreeNode(val);
        TreeNode prev = null, cur = root;
        while (cur != null && cur.val > val) {prev = cur; cur = cur.right;}
        if (prev == null) {
            node.left = cur;
            return node;
        } else {
            prev.right = node;
            node.left = cur;
            return root;
        }
    }
}

Typescript 代码：

function insertIntoMaxTree(root: TreeNode | null, val: number): TreeNode | null {const node = new TreeNode(val)
    let prev = null, cur = root
    while (cur != null && cur.val > val) {prev = cur; cur = cur.right}
    if (prev == null) {
        node.left = root
        return node
    } else {
        prev.right = node
        node.left = cur
        return root
    }
};

工夫复杂度：$O(n)$
空间复杂度：$O(1)$

这是咱们「刷穿 LeetCode」系列文章的第 No.998 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的合集新基地 🎉🎉

本文由 mdnice 多平台公布

关于后端:998-最大二叉树-II-常规模拟题

题目形容

模仿

最初