998. 最大二叉树 II
最大树定义:一个树,其中每个节点的值都大于其子树中的任何其他值。
给出最大树的根节点 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
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-binary-tree-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
根据示例可以看出附加值val加在数组末尾,即加在树的右边,只用考虑右子树。
如果val大于右子树原根结点,则原根放到新根左侧。如果小则在右子树迭代。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode insertIntoMaxTree(TreeNode root, int val) {
TreeNode node = new TreeNode(val);
node.left = null;
node.right = null;
if (root == null)
return node;
if (root.val < val)
{
node.left = root;
return node;
} TreeNode p =root;
while (p.right != null && p.right.val > val)
p = p.right;
TreeNode temp = p.right;
p.right = node;
node.left = temp;
return root;
}
}
最新文章
- jQuery弹出提示信息简洁版(自动消失)
- 学习.Net的经典网站
- Linux 信号详解六(可靠信号与不可靠信号)
- Extjs ComboBox 动态选中第一项
- composer未升级报错
- c语言字符串库函数#include<;string.h>;
- ThreadLocal笔记
- 初识webpack——webpack四个基础概念
- JAVA的单元测试技术
- 【转】重写Equals为什么要同时重写GetHashCode
- ubuntu 14.04zabbix的安装
- CODEFORCES掉RATING记 #3
- Java并发程序设计(十)设计模式与并发之Future模式
- 解决ubuntu系统“XXX is not in the sudoers file”错误
- [No0000FC]C# 预处理器指令
- 2016年蓝桥杯省赛A组c++第8题(暴力求解)
- 通过AnimationSet设置动画
- HDU_6043_KazaQ&#39;s Socks
- mysql 运行 sql 脚本
- JS BOM对象 History对象 Location对象