每日一练:LeeCode-654、最大二叉树【二叉树+DFS+分治】

这篇具有很好参考价值的文章主要介绍了每日一练:LeeCode-654、最大二叉树【二叉树+DFS+分治】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本文是力扣LeeCode-654、最大二叉树【二叉树+DFS+分治】 学习与理解过程,本文仅做学习之用,对本题感兴趣的小伙伴可以出门左拐LeeCode。

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

创建一个根节点其值为 nums 中的最大值
递归地在最大值 左边 的 子数组前缀上 构建左子树
递归地在最大值 右边 的 子数组后缀上 构建右子树
返回 nums 构建的 最大二叉树

示例 1:
每日一练:LeeCode-654、最大二叉树【二叉树+DFS+分治】,# 每日一道LeeCode算法题,数据结构,算法,leetcode

输入: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:

输入:nums = [3,2,1]
输出:[3,null,2,null,1]

提示:

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

思路

本题的思路:找到不断更新区间的中的最大值,以这个最大值为根节点,并且以此为其左右子树的分界点,不断递归构造树结构

递归法

构造树采⽤的是前序遍历,因为先构造中间节点,然后递归构造左⼦树和右⼦树

1、确定递归函数的参数和返回值

TreeNode qianBianLi(int[] nums,int left,int right)

2、确定终⽌条件

if(left>=right)return null; //不满足下标判断,直接返回null的子节点即可

3、确定单层递归的逻辑

  • 先要找到数组中最⼤的值和对应的下标
  • 最⼤的值构造根节点,并以当前根节点作为左子树递归的右边界、以当前根节点作为右子树递归的左边界来构建树结构
        int maxIndexValue = left;   // 分割点下标:maxValueIndex
        for (int i=left+1;i<right;i++){
            if (nums[i]>nums[maxIndexValue])maxIndexValue=i;
        }

        TreeNode root = new TreeNode(nums[maxIndexValue]);  // 左闭右开:[left, maxValueIndex)
        root.left = qianBianLi(nums,left,maxIndexValue);    // 左闭右开:[maxValueIndex + 1, right)
        root.right = qianBianLi(nums,maxIndexValue+1,right);
        return root;

整体代码

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return qianBianLi(nums,0,nums.length);
    }

    // 在左闭右开区间[left, right),构造⼆叉树
    TreeNode qianBianLi(int[] nums,int left,int right){
        if(left>=right)return null; //不满足下标判断,直接返回null的子节点即可

        int maxIndexValue = left;   // 分割点下标:maxValueIndex
        for (int i=left+1;i<right;i++){
            if (nums[i]>nums[maxIndexValue])maxIndexValue=i;
        }

        TreeNode root = new TreeNode(nums[maxIndexValue]);  // 左闭右开:[left, maxValueIndex)
        root.left = qianBianLi(nums,left,maxIndexValue);    // 左闭右开:[maxValueIndex + 1, right)
        root.right = qianBianLi(nums,maxIndexValue+1,right);
        return root;
    }
}

最重要的一句话:做二叉树的题目,首先需要确认的是遍历顺序
大佬们有更好的方法,请不吝赐教,谢谢
文章来源地址https://www.toymoban.com/news/detail-833568.html

到了这里,关于每日一练:LeeCode-654、最大二叉树【二叉树+DFS+分治】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 654. 最大二叉树

    思路: https://leetcode.cn/problems/maximum-binary-tree/solution/zui-da-er-cha-shu-by-leetcode-solution-lbeo/

    2024年02月11日
    浏览(72)
  • C++力扣题目654--最大二叉树

    给定一个不重复的整数数组  nums  。  最大二叉树  可以用下面的算法从  nums  递归地构建: 创建一个根节点,其值为  nums  中的最大值。 递归地在最大值  左边  的  子数组前缀上  构建左子树。 递归地在最大值  右边  的  子数组后缀上  构建右子树。 返回  nums  构

    2024年01月20日
    浏览(38)
  • 【算法与数据结构】654、LeetCode最大二叉树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树这两道题有些类似,相关代码可以互相参考,本题明示了要用递归来做,那么递归三要素不可缺少: 输入参数和返

    2024年02月09日
    浏览(44)
  • leecode104——二叉树的最大深度

    左子树与右子树的最大深度可以通过递归遍历(深度优先搜索)得到,首先: 递归三部曲:(1)确定递归的参数和返回值,因为要比较的是左右子树的最大深度,所以每次传入的根节点,返回最大深度,即int类型的数字 (2)递归的终止条件:当跟节点为空,说明高度为0或

    2024年02月03日
    浏览(37)
  • 算法训练day20Leetcode654最大二叉树617合并二叉树700二叉树中的1搜索98验证二叉搜索树

    https://leetcode.cn/problems/maximum-binary-tree/description/ 中序遍历递归,找到最大值然后作为根节点 凡是构造二叉树的题目都用前序遍历 (中左右) 为先构造中间节点,然后递归构造左子树和右子树。 确定递归函数的参数和返回值 参数传入的是存放元素的数组,返回该数组构造的二

    2024年01月21日
    浏览(40)
  • 【算法刷题day20】Leetcode:654. 最大二叉树、617.合并二叉树、700. 二叉搜索树中的搜索、98.验证二叉搜索树

    草稿图网站 java的Deque 题目: 654. 最大二叉树 解析: 代码随想录解析 解题思路 NLR的建树 代码 总结 暂无 题目: 617.合并二叉树 解析: 代码随想录解析 解题思路 如果都为root1, root2都为空,返回null;如果root1为空,root2不为空,返回root2;如果roo1不为空,root2为空,返回root

    2024年04月10日
    浏览(38)
  • 每日OJ题_二叉树dfs③_力扣814. 二叉树剪枝

    目录 力扣814. 二叉树剪枝 解析代码 814. 二叉树剪枝 难度 中等 给你二叉树的根结点  root  ,此外树的每个结点的值要么是  0  ,要么是  1  。 返回移除了所有不包含  1  的子树的原二叉树。 节点  node  的子树为  node  本身加上所有  node  的后代。 示例 1: 示例 2: 示

    2024年02月22日
    浏览(38)
  • C/C++每日一练(20230410) 二叉树专场(4)

    目录 1. 二叉搜索树迭代器  🌟🌟🌟 2. 验证二叉搜索树  🌟🌟🌟 3. 不同的二叉搜索树 II  🌟🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 实现一个二叉搜索树迭代器类 BSTIterator  ,表示一个按中序遍历二

    2023年04月12日
    浏览(24)
  • C/C++每日一练(20230513) 二叉树专场(7)

    目录 1. 翻转二叉树  🌟 2. 二叉树的最小深度  🌟 3. 填充每个节点的下一个右侧节点指针  🌟🌟 附:二叉树的序列化与反序列化 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 翻转一棵二叉树。 示例: 输入: 输

    2024年02月04日
    浏览(27)
  • C/C++每日一练(20230427) 二叉树专场(5)

    目录 1. 从中序与后序遍历序列构造二叉树  🌟🌟 2. 从先序与中序遍历序列构造二叉树  🌟🌟 3. 二叉树展开为链表  🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 根据一棵树的中序遍历与后序遍历构造二叉

    2024年02月01日
    浏览(25)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包