题目大意：
最大二叉树 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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=998
解题思路分析：
本题是LEETCODE 654. Maximum Binary Tree的续集，如果你没做过第一题，那么你可能会对本题的题目感到有些陌生和混乱，而本文的讲解也是基于上一题目的思路进阶而来，因此强烈建议你先刷一下本系列的第一集内容。
回到本题，题目给出的参数实际上是上一题目的返回结果，也就是说你需要执行上一题目的逆运算，通过一颗最大树，求出原始数组，然后再在原始数组后面加上一个数字val，最后再按照第一题的思路求出新的最大树。
因此本题的重点是如何通过最大树反向求出数组。实现逻辑大致如下：
- 先统计出二叉树中的节点数量。统计节点数量的方式很多，以dfs递归为例：从根节点开始向下做dfs搜索，根节点下方节点总数量为根节点数量1加上左子树节点总数与右子树节点总数，而两个子树的节点数量可以dfs递归至子问题去求解。dfs递归的终止条件为当前节点为空时，返回0。
- 利用求出的节点数量count再加上1作为返回数组长度，建立返回数组res[]。加一的目的是加上附加值val，因此res[]的最后一位应该是val。
- 还是利用递归方式，将最大树还原为数组。递归函数的参数为当前节点对象以及该节点所在数组的范围。还是从根节点开始，他所在数组的范围为0到数组长度减一范围。递归中，首先查看左子树的节点个数leftCount（方法与第一步相同），左边界加上leftCount即是当前节点所在的下标处，更新数组中该下标的值为当前节点。接下来递归至左子树，左子树所在范围应该是当前左边界left到left+leftCount-1范围。同理右子树应该在left+leftCount+1到right范围内。递归终止条件为当前节点为空。
- 数组已还原，接下来的代码与第一题完全一致。
实现代码：
public TreeNode insertIntoMaxTree(TreeNode root, int val) {
int count=count(root); // 所有节点个数
int[] arr=new int[count+1]; // 新建返回数组
arr[count]=val; // 数组末位是val
createArr(root,0,count,arr); // 还原数组
return help(arr,0,count); // 构建新的最大树
}
int count(TreeNode root){
if(root==null) return 0;
int count=1+count(root.left)+count(root.right);
return count;
}
void createArr(TreeNode root, int l, int r, int[] arr){
if(root==null) return; // 节点对象为空时，结束递归
int leftCount=count(root.left); // 查看右子树节点个数
int rootIndex=l+leftCount; // 通过右子树节点个数计算出当前节点位置
arr[rootIndex]=root.val; // 更新该下标为当前节点值
createArr(root.left,l,rootIndex-1,arr); // 递归还原左子树
createArr(root.right,rootIndex+1,r,arr); // 递归还原右子树
}
TreeNode help(int[] nums, int left, int right){
if(left>right) return null; // 非法区间，返回null
int maxIndex=max(nums,left,right); // 找到区间内最大值所在下标
TreeNode node=new TreeNode(nums[maxIndex]); // 利用区间最大值构建当前节点
node.left=help(nums,left,maxIndex-1); // 递归构建左子节点
node.right=help(nums,maxIndex+1,right); // 递归构建右子节点
return node; // 返回当前节点
}
// 找到区间内最大值
int max(int[] nums, int left,int right){
int maxIndex=left;
for(int i=left;i<=right;i++){
if(nums[i]>nums[maxIndex]){
maxIndex=i;
}
}
return maxIndex;
}本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Maximum Binary Tree II.
Memory Usage: 37.5 MB, less than 70.59% of Java online submissions for Maximum Binary Tree II.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-998-maximum-binary-tree-ii-解题思路分析/