萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣第654题-最大二叉树

发表于 2022-08-21 | 分类于 力扣刷题 | 0 | 阅读次数 71

题目描述

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点,其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

原题链接

提示:
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums 中的所有整数 互不相同

样例

示例 1:
image.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:
image.png
输入:nums = [3,2,1]
输出:[3,null,2,null,1]

题目评估

知识点:栈、树、数组、分治、二叉树、单调栈
难度:中等

分析

本题使用分支递归解题,找到当前数组中最大值递归最大值左边的数组和右边的数组并连接在左子树和右子树。

Java代码题解

分治递归:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return plantTrees(nums, 0, nums.length - 1);
    }
    
    // 递归方法
    private TreeNode plantTrees(int[] nums, int start, int end) {
        int rootIndex = findMaxIndex(nums, start, end);
        TreeNode root = new TreeNode(nums[rootIndex]);
        if (start < rootIndex) {
            root.left = plantTrees(nums, start, rootIndex - 1);
        }
        if (end > rootIndex) {
            root.right = plantTrees(nums, rootIndex + 1, end);
        }
        return root;
    }
    
    // 找到数组中的最大值的下标
    private int findMaxIndex(int[] nums, int start, int end) {
        int max = Integer.MIN_VALUE;
        int index = start;
        for (int i = start; i <= end; i++) {
            if (nums[i] > max) {
                max = nums[i];
                index = i;
            }
        }
        return index;
    }
    
}

单调栈:


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return monotonicallyStack(nums);
    }

    private TreeNode monotonicallyStack(int[] nums) {
        // 单调栈
        TreeNode[] stack = new TreeNode[nums.length];
        // 栈顶指针
        int point = 0;
        for (int n : nums) {
            // 当前节点
            TreeNode tn = new TreeNode(n);
            // 当栈顶元素小于当前值,不断弹栈,将当前元素的left指向栈顶元素
            while (point > 0 && stack[point - 1].val < n) {
                tn.left = stack[point - 1];
                // 栈顶指针下移
                point--;
            }
            // 栈内有节点,一定比当前值大,把栈顶元素的right指向当前元素
            if (point > 0) {
                stack[point - 1].right = tn;
            }
            // 当前元素入栈
            stack[point] = tn;
            point++;
        }
        return stack[0];
    }

}

复杂度分析

分治递归:
时间复杂度:O(n^2)
空间复杂度:O(n)

单调栈:
时间复杂度:O(n)
空间复杂度:O(n)

# 算法 # 程序设计 # 分治算法 # 力扣
力扣剑指Offer 19-正则表达式匹配
RabbitMQ基础学习
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

77 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持