X

LEETCODE 998. Maximum Binary Tree II 解题思路分析

题目大意:

最大二叉树 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-解题思路分析/
Categories: leetcode
kwantong: