关于后端: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 多平台公布