最大二叉树lt-654

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:

二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树,并且输出这个树的根节点。

这道题其实有点像有先序遍历和中序遍历构造二叉树,给了树根节点的值和左右子树的构造方式,以此来构造二叉树。

 public static TreeNode constructMaximumBinaryTree(int[] nums) {
        return recursion(nums, 0, nums.length - 1);
    }

    public static TreeNode recursion(int[] nums, int start, int end) {
        //结束递归条件
        if (start > end) {
            return null;
        }
        //这个判断也可以不要 
        if (start == end) {
            return new TreeNode(nums[start]);
        }
            int max = nums[start];
            int k = start;
            for (int i = start; i <= end; i++) {
                if (max <= nums[i]) {
                    k = i;
                    max = nums[i];
                }
            }
            TreeNode root = new TreeNode(max);
            root.left = recursion(nums, start, k - 1);
            root.right = recursion(nums, k + 1, end);
            return root;
    }

  

上一篇:【操作系统】线程


下一篇:CF1093A Dice Rolling 题解