Java 求解最大二叉树-蒲公英云

Java 求解最大二叉树

文章目录

- 一、题目
- 二、递归分析
- 三、总结

一、题目

给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的最大二叉树定义如下：

二叉树的根是数组 nums 中的最大元素。
左子树是通过数组中最大值左边部分递归构造出的最大二叉树。
右子树是通过数组中最大值右边部分递归构造出的最大二叉树。

在这里插入图片描述

二、递归分析

题目要求构建最大二叉树，需要每次从数组中寻找处最大值，然后以该最大值为根节点，划分左右数组，继续构建

采用递归法进行解决

（1）确定递归参数和返回值

为了方便，采用记录数组索引，实现每次从数组找出最大值进行构建

createMaxBinaryTree(nums, 0, nums.length - 1);

（2）确定递归终止条件

当左边界大于右边界时表明待处理数组为空，终止

（3）确定单层递归逻辑

待处理数组中寻找到最大值对应的下标，创建该值对应的根节点，再递归创建该值的左子树，递归创建该值的右子树

class Solution { 
    public TreeNode constructMaximumBinaryTree(int[] nums) { 
        //数组，待处理数组的左边界，待处理数组的右边界
        return createMaxBinaryTree(nums, 0, nums.length - 1);
    }
    public TreeNode createMaxBinaryTree(int[] nums, int begin, int end) { 
        if (begin > end) { 
            return null;
        }
        //记录最大值的下标
        int maxIndex = begin;
        //寻找最大值
        for (int i = begin; i <= end; i++) { 
            if (nums[i] > nums[maxIndex]) { 
                maxIndex = i;
            }
        }
        //创建根节点
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = createMaxBinaryTree(nums, begin, maxIndex - 1);
        root.right = createMaxBinaryTree(nums, maxIndex + 1, end);
        return root;
    }
}