関小君刷题记

题目大意：

最大二叉树 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. 1 <= B.length <= 100

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=998

解题思路分析：

本题是LEETCODE 654. Maximum Binary Tree的续集，如果你没做过第一题，那么你可能会对本题的题目感到有些陌生和混乱，而本文的讲解也是基于上一题目的思路进阶而来，因此强烈建议你先刷一下本系列的第一集内容。

回到本题，题目给出的参数实际上是上一题目的返回结果，也就是说你需要执行上一题目的逆运算，通过一颗最大树，求出原始数组，然后再在原始数组后面加上一个数字val，最后再按照第一题的思路求出新的最大树。

因此本题的重点是如何通过最大树反向求出数组。实现逻辑大致如下：

1. 先统计出二叉树中的节点数量。统计节点数量的方式很多，以dfs递归为例：从根节点开始向下做dfs搜索，根节点下方节点总数量为根节点数量1加上左子树节点总数与右子树节点总数，而两个子树的节点数量可以dfs递归至子问题去求解。dfs递归的终止条件为当前节点为空时，返回0。
2. 利用求出的节点数量count再加上1作为返回数组长度，建立返回数组res[]。加一的目的是加上附加值val，因此res[]的最后一位应该是val。
3. 还是利用递归方式，将最大树还原为数组。递归函数的参数为当前节点对象以及该节点所在数组的范围。还是从根节点开始，他所在数组的范围为0到数组长度减一范围。递归中，首先查看左子树的节点个数leftCount（方法与第一步相同），左边界加上leftCount即是当前节点所在的下标处，更新数组中该下标的值为当前节点。接下来递归至左子树，左子树所在范围应该是当前左边界left到left+leftCount-1范围。同理右子树应该在left+leftCount+1到right范围内。递归终止条件为当前节点为空。
4. 数组已还原，接下来的代码与第一题完全一致。

实现代码：

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.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-998-maximum-binary-tree-ii-解题思路分析/