最大树 定义:一棵树,并满足:其中每个节点的值都大于其子树中的任何其他值。
给你最大树的根节点 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
附加值始终在列表末尾,只可能是
var insertIntoMaxTree = function(root, val) { // 可选链操作符 ?.
if (root.val < val) return new TreeNode(val, root)
;(function d(n) {
if (n.right?.val > val) return d(n.right)
n.right = new TreeNode(val, n.right)
})(root)
return root
};
function insertIntoMaxTree(root: TreeNode | null, val: number): TreeNode | null {
const d = n => n.right?.val > val ? d(n.right) : n.right = new TreeNode(val, n.right)
return root.val < val ? new TreeNode(val, root) : (d(root), root)
};
class Solution {
function d($n, $val) {
if ($n->right && $n->right->val > $val) return $this->d($n->right, $val);
$n->right = new TreeNode($val, $n->right);
}
function insertIntoMaxTree($root, $val) {
if ($root->val < $val) return new TreeNode($val, $root);
$this->d($root, $val);
return $root;
}
}
func d(n *TreeNode, val int) {
if n.Right != nil && n.Right.Val > val {
d(n.Right, val)
return
}
n.Right = &TreeNode{val, n.Right, nil}
}
func insertIntoMaxTree(root *TreeNode, val int) *TreeNode {
if root.Val < val {
return &TreeNode{val, root, nil}
}
d(root, val)
return root
}
class Solution {
public void d(TreeNode n, int val) {
if (n.right != null && n.right.val > val) d(n.right, val);
else n.right = new TreeNode(val, n.right, null);
}
public TreeNode insertIntoMaxTree(TreeNode root, int val) {
if (root.val < val) return new TreeNode(val, root, null);
d(root, val);
return root;
}
}
public class Solution {
public void D(TreeNode n, int val) {
if (n.right != null && n.right.val > val) D(n.right, val);
else n.right = new TreeNode(val, n.right);
}
public TreeNode InsertIntoMaxTree(TreeNode root, int val) {
if (root.val < val) return new TreeNode(val, root);
D(root, val);
return root;
}
}
void d(struct TreeNode* n, int val) {
if (n->right && n->right->val > val) return d(n->right, val);
struct TreeNode* obj = malloc(sizeof(struct TreeNode));
obj->val = val;
obj->left = n->right;
obj->right = NULL;
n->right = obj;
}
struct TreeNode* insertIntoMaxTree(struct TreeNode* root, int val){
if (root->val < val) {
struct TreeNode* obj = malloc(sizeof(struct TreeNode));
obj->val = val;
obj->left = root;
obj->right = NULL;
return obj;
}
d(root, val);
return root;
}
class Solution:
def d(self, n: Optional[TreeNode], val: int):
if n.right and n.right.val > val: return self.d(n.right, val)
n.right = TreeNode(val, n.right)
def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if root.val < val: return TreeNode(val, root)
self.d(root, val)
return root
var insertIntoMaxTree = function(root, val) {
if (root === null || root.val < val) return new TreeNode(val, root)
root.right = insertIntoMaxTree(root.right, val)
return root
};
function insertIntoMaxTree(root: TreeNode | null, val: number): TreeNode | null {
if (root == null || root.val < val) return new TreeNode(val, root)
root.right = insertIntoMaxTree(root.right, val)
return root
};
class Solution {
function insertIntoMaxTree($root, $val) {
if ($root === null || $root->val < $val) return new TreeNode($val, $root);
$root->right = $this->insertIntoMaxTree($root->right, $val);
return $root;
}
}
func insertIntoMaxTree(root *TreeNode, val int) *TreeNode {
if root == nil || root.Val < val {
return &TreeNode{val, root, nil}
}
root.Right = insertIntoMaxTree(root.Right, val)
return root
}
class Solution {
public TreeNode insertIntoMaxTree(TreeNode root, int val) {
if (root == null || root.val < val) return new TreeNode(val, root, null);
root.right = insertIntoMaxTree(root.right, val);
return root;
}
}
public class Solution {
public TreeNode InsertIntoMaxTree(TreeNode root, int val) {
if (root == null || root.val < val) return new TreeNode(val, root);
root.right = InsertIntoMaxTree(root.right, val);
return root;
}
}
struct TreeNode* insertIntoMaxTree(struct TreeNode* root, int val){
if (root == NULL || root->val < val) {
struct TreeNode* obj = malloc(sizeof(struct TreeNode));
obj->val = val;
obj->left = root;
obj->right = NULL;
return obj;
}
root->right = insertIntoMaxTree(root->right, val);
return root;
}
class Solution:
def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if root == None or root.val < val: return TreeNode(val, root)
root.right = self.insertIntoMaxTree(root.right, val)
return root
var insertIntoMaxTree = function(root, val) {
if (root.val < val) return new TreeNode(val, root)
const r = root
while (root.right?.val > val) root = root.right
root.right = new TreeNode(val, root.right)
return r
};
var insertIntoMaxTree = function(root, val) {
const r = root
while (root.right?.val > val) root = root.right
return root.val < val ? new TreeNode(val, root) : (root.right = new TreeNode(val, root.right), r)
};
class Solution {
function insertIntoMaxTree($root, $val) {
if ($root->val < $val) return new TreeNode($val, $root);
$r = $root;
while ($root->right && $root->right->val > $val) $root = $root->right;
$root->right = new TreeNode($val, $root->right);
return $r;
}
}
func insertIntoMaxTree(root *TreeNode, val int) *TreeNode {
if root.Val < val {
return &TreeNode{val, root, nil}
}
r := root
for root.Right != nil && root.Right.Val > val {
root = root.Right
}
root.Right = &TreeNode{val, root.Right, nil}
return r
}
class Solution {
public TreeNode insertIntoMaxTree(TreeNode root, int val) {
if (root.val < val) return new TreeNode(val, root, null);
TreeNode r = root;
while (root.right != null && root.right.val > val) root = root.right;
root.right = new TreeNode(val, root.right, null);
return r;
}
}
public class Solution {
public TreeNode InsertIntoMaxTree(TreeNode root, int val) {
if (root.val < val) return new TreeNode(val, root);
TreeNode r = root;
while (root.right != null && root.right.val > val) root = root.right;
root.right = new TreeNode(val, root.right);
return r;
}
}
struct TreeNode* insertIntoMaxTree(struct TreeNode* root, int val){
if (root->val < val) {
struct TreeNode* obj = malloc(sizeof(struct TreeNode));
obj->val = val;
obj->left = root;
obj->right = NULL;
return obj;
}
struct TreeNode* r = root;
while (root->right && root->right->val > val) root = root->right;
struct TreeNode* obj = malloc(sizeof(struct TreeNode));
obj->val = val;
obj->left = root->right;
obj->right = NULL;
root->right = obj;
return r;
}
class Solution:
def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if root.val < val: return TreeNode(val, root)
r = root
while root.right and root.right.val > val: root = root.right
root.right = TreeNode(val, root.right)
return r