（js）leetcode 654. 最大二叉树

刺骨的言语ヽ痛彻心扉 2022-11-10 14:29 116阅读 0赞

### 题目： ###

> 给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
> 
> 二叉树的根是数组 nums 中的最大元素。  
> 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。  
> 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。  
> 返回有给定数组 nums 构建的 最大二叉树 。
> 
> 示例 1：
> 
> ![b29cadd77dc8885a770726468eec2d67.png][]  
> 输入：nums = \[3,2,1,6,0,5\]  
> 输出：\[6,3,5,null,2,0,null,null,1\]  
> 解释：递归调用如下所示：  
> \- \[3,2,1,6,0,5\] 中的最大值是 6 ，左边部分是 \[3,2,1\] ，右边部分是 \[0,5\] 。  
>     - \[3,2,1\] 中的最大值是 3 ，左边部分是 \[\] ，右边部分是 \[2,1\] 。  
>         - 空数组，无子节点。  
>         - \[2,1\] 中的最大值是 2 ，左边部分是 \[\] ，右边部分是 \[1\] 。  
>             - 空数组，无子节点。  
>             - 只有一个元素，所以子节点是一个值为 1 的节点。  
>     - \[0,5\] 中的最大值是 5 ，左边部分是 \[0\] ，右边部分是 \[\] 。  
>         - 只有一个元素，所以子节点是一个值为 0 的节点。  
>         - 空数组，无子节点。  
> 示例 2：
> 
> ![6bd1e20db72784d568f327a28f14a9ee.png][]  
> 输入：nums = \[3,2,1\]  
> 输出：\[3,null,2,null,1\]
> 
> 提示：
> 
> 1 <= nums.length <= 1000  
> 0 <= nums\[i\] <= 1000  
> nums 中的所有整数 互不相同

### 思路： ###

> 1. 找到数组中的最大值
> 
> 2. 递归调用构造左右子树

### 代码实现： ###

/**
     * Definition for a binary tree node.
     * function TreeNode(val, left, right) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.left = (left===undefined ? null : left)
     *     this.right = (right===undefined ? null : right)
     * }
     */
    /**
     * @param {number[]} nums
     * @return {TreeNode}
     */
    var constructMaximumBinaryTree = function (nums) {
        return build(nums, 0, nums.length - 1);
    };
    
    // 将 nums[lo...hi] 构造成符合条件的树，返回根节点
    var build = function (nums, lo, hi) {
        if (lo > hi) {
            return null;
        }
        // 找到数组中的最大值和对应的索引
        let index = -1, maxValue = -Infinity;
        for (let i = lo; i <= hi; i++) {
            if (maxValue < nums[i]) {
                index = i;
                maxValue = nums[i];
            }
        }
    
        let root = new TreeNode(maxValue);
        // 递归调用构造左右子树
        root.left = build(nums, lo, index - 1);
        root.right = build(nums, index + 1, hi);
    
        return root;
    }

### 运行结果： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70][]

[b29cadd77dc8885a770726468eec2d67.png]: /images/20221022/5a64be16efa84ad383e47e70d532072c.png
[6bd1e20db72784d568f327a28f14a9ee.png]: https://img-blog.csdnimg.cn/img_convert/6bd1e20db72784d568f327a28f14a9ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210318224414213.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl,size_16,color_FFFFFF,t_70