Java 求解最大二叉树

一时失言乱红尘 2022-10-17 00:43 136阅读 0赞

### 文章目录 ###

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

## 一、题目 ##

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]

## 二、递归分析 ##

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

采用递归法进行解决

（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;
        }
    }

## 三、总结 ##

**该题适用递归解决，同时对于每段数组的划分处理，如果采用数组复制解决，效率低下，可以采用不处理数组，记录数组下标进行处理**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]: /images/20221014/59542b969402448da321e28e1aa8d9d3.png