原文链接: https://leetcode-cn.com/problems/maximum-binary-tree-ii

英文原文

A maximum tree is a tree where every node has a value greater than any other value in its subtree.

You are given the root of a maximum binary tree and an integer val.

Just as in the previous problem, the given tree was constructed from a list a (root = Construct(a)) recursively with the following Construct(a) routine:

• If a is empty, return null.
• Otherwise, let a[i] be the largest element of a. Create a root node with the value a[i].
• The left child of root will be Construct([a[0], a[1], ..., a[i - 1]]).
• The right child of root will be Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]]).
• Return root.

Note that we were not given a directly, only a root node root = Construct(a).

Suppose b is a copy of a with the value val appended to it. It is guaranteed that b has unique values.

Return Construct(b).

 

Example 1:

Input: root = [4,1,3,null,null,2], val = 5
Output: [5,4,null,1,3,null,null,2]
Explanation: a = [1,4,2,3], b = [1,4,2,3,5]

Example 2:

Input: root = [5,2,4,null,1], val = 3
Output: [5,2,4,null,1,null,3]
Explanation: a = [2,1,5,4], b = [2,1,5,4,3]

Example 3:

Input: root = [5,2,3,null,1], val = 4
Output: [5,2,4,null,1,3]
Explanation: a = [2,1,5,3], b = [2,1,5,3,4]

 

Constraints:

• The number of nodes in the tree is in the range [1, 100].
• 1 <= Node.val <= 100
• All the values of the tree are unique.
• 1 <= val <= 100

中文题目

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

给出最大树的根节点 root。

就像之前的问题那样，给定的树是从列表 A（root = Construct(A)）递归地使用下述 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 <= B.length <= 100

 

 

通过代码

高赞题解

方法：递归算法

题意分析
已知最大树A，插入一个值val后，返回插入后的树

思路及算法
树，基本都可以递归解决。且递归只需 7 行代码，不需创建副本，相当简洁。

这道题主要需要理解 树 和 数组 这两者的构造关系。关系不太理解的可参考 如何构建最大树。
题目中的描述为：

1. 最大树的数组中，在节点 root 中右侧的元素，是右子树的元素
2. B 树是在 A 树的基础上，将 val 值放在数组的最后面。**->** 出现在右侧说明，只要 val 不比前面的 root 大，就要在右子树递归。

因此，递归时直到 val 找到了合适的位置（即 val 小于某一个 root 的值），那么在此之前， val 一定在该 root 的右侧。

将该逻辑演绎为代码，递归的判断方式为：

• 如果是最大数，则将 root 放在左边
• 否则一直是在右子树递归（由最大树的定义决定，在 root 中的最大值右侧的是右子树的元素），直到找到比 val 大的数

代码

public TreeNode insertIntoMaxTree(TreeNode root, int val) {
    if(root == null || root.val < val) {
        TreeNode tmp = new TreeNode(val);
        tmp.left = root;
        return tmp;
    }
    root.right = insertIntoMaxTree(root.right, val);
    return root;
}

拓展
另有 数组 与 树 的构造转化，可适当参考练习递归。

• 数组转树：654. 最大二叉树，可参考递归建树
• 427. 建立四叉树 ：可参考递归

结语
如果对您有帮助，欢迎点赞、收藏、关注 沪里户外，让更多的小伙伴看到，祝大家offer多多，AC多多！

统计信息

通过次数	提交次数	AC比率
7944	12870	61.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
最大二叉树	中等