首页 > 编程语言 >算法力扣刷题记录 五十一【654.最大二叉树】

算法力扣刷题记录 五十一【654.最大二叉树】

时间:2024-07-18 11:56:47浏览次数:26  
标签:right TreeNode nums int 654 五十一 二叉树 root left

前言

二叉树篇,继续。
记录 五十一【654.最大二叉树】


一、题目阅读

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

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

示例 1:
在这里插入图片描述

输入: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. 题目定义如何构建最大二叉树,按照题目的递归思路即可以实现。
  2. 递归返回值:返回子树(树)的根节点;
  3. 递归参数:左子树/右子树的数组,所以参数vector< int >
  4. 递归终止条件:当数组为空,返回nullptr;当数组只有一个,可直接返回叶子节点(等同于根节点)。
  5. 递归逻辑:
  • 找到最大值。
  • 分割nums。
  1. 总结:整体思路类似记录 五十【106.从中序与后序遍历序列构造二叉树】拿到中间节点后分割中序数组。

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if(nums.size() == 0) return nullptr;

        if(nums.size() == 1){   //叶子自己就是根
            TreeNode* root = new TreeNode(nums[0]);
            return root;
        }
        //找最大值确定根节点,同时确定最大值的下标index
        int maxnum = INT_MIN;
        int index = 0;
        for(int i = 0;i < nums.size();i++){
            if(nums[i] > maxnum){
                maxnum = nums[i];
                index = i;
            }
        }
        TreeNode* root = new TreeNode(maxnum);
        //区间左闭右开
        vector<int> left(nums.begin(),nums.begin()+index);
        vector<int> right(nums.begin()+index+1,nums.end());
        root->left = constructMaximumBinaryTree(left);
        root->right = constructMaximumBinaryTree(right);
        return root;
    }
};

三、参考学习

参考学习链接

学习内容

  1. 题目属于构造二叉树类型,遍历顺序:前序——中左右。类似:记录 五十【106.从中序与后序遍历序列构造二叉树】 ,同理构造顺序——中左右。

  2. 思路同理。和二、中的思路一致。但是有点区别——如果终止条件判断nums是否为空,那么“传递”下一层不用判断index值;如果终止条件默认nums不为空,那么“传递”下一层要if(index条件)。

  3. 代码优化:不创建新数组传递。只传递下标值

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        TreeNode* build(vector<int>& nums,int begin,int end){
            if(begin == end) return nullptr;
            if(end - begin == 1){
                TreeNode* root = new TreeNode(nums[begin]);
                return root;
            }
    
            int maxvalue = 0;//因为题目中说元素值最小是0
            int index = begin;//从begin开始判断
            for(int i = begin;i < end;i++){
                if(nums[i] > maxvalue){
                    maxvalue = nums[i];
                    index = i;
                }
            }
    
            int leftbegin = begin;
            int leftend = index;
            int rightbeign = index+1;
            int rightend = end;
    
            TreeNode* root = new TreeNode(maxvalue);
            root->left = build(nums,leftbegin,leftend);
            root->right = build(nums,rightbeign,rightend);
            return root;
        }
        TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
            return build(nums,0,nums.size());
        }
    };
    

总结

记录 五十一【654.最大二叉树】和记录 五十【106.从中序与后序遍历序列构造二叉树】可以归为一类。

可以改进成:只传递下标值,每次不创建新数组,不开辟新空间更好

(欢迎指正,转载标明出处)

标签:right,TreeNode,nums,int,654,五十一,二叉树,root,left
From: https://blog.csdn.net/danaaaa/article/details/140518025

相关文章

  • 算法力扣刷题记录 五十【106.从中序与后序遍历序列构造二叉树】和【105.从前序与中序
    前言记录三十八的四、二叉树构建通过层序遍历的数组实现。层序遍历中,某个节点下标是i,那么左孩子的下标2i+1,右孩子的下标2i+2。这是统一的规律。那么通过中序序列和后序序列如何构造二叉树?通过中序序列和前序序列如何构造二叉树?通过前序序列和后序序列如何构造二叉树?一......
  • 从前序与中序遍历序列构造二叉树-递归
    题目描述:个人题解:        只要我们在中序遍历中定位到根节点,那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的,因此我们就可以对应到前序遍历的结果中,对上述形式中的所有左右括号进行定位。这样的话,我们就......
  • Java二叉树经典例题
    目录一.相同的树二.翻转二叉树三.平衡二叉树四.对称二叉树五.根据前(后)和中序排序构建二叉树1.前序和中序构建2.后序和中序构建六.二叉树的层序遍历七.二叉树非递归遍历1.前序遍历2.中序遍历3.后序遍历八.总结前言:前面说过树是通过递归定义的。做二叉树的题,递......
  • 树与二叉树
    树与二叉树目录树与二叉树基本概念基本术语根双亲结点孩子节点节点的层次节点的度叶子树的高度有序树与无序树二叉树二叉树概念:二叉树基本特性满二叉树/完美二叉树:完全二叉树:平衡二叉树:退化二叉树:二叉树的链式存储树的遍历BST树基本概念插入节点删除节点遍历代码基本概念树是一......
  • 题解:P10722 [GESP202406 六级] 二叉树
    题意一颗\(n\)节点的二叉树,每个节点非黑即白,给你\(Q\)次操作,每次给你一个\(u\),把\(u\)的子树内所有节点颜色反转,问最终每个节点的颜色。分析看到数据范围,首先把操作离线。容易发现如果一个节点重复操作奇数次,等效于操作一次,如果重复操作偶数次,等效于没操作。所以我们可......
  • leetcode145. 二叉树的后序遍历,递归法+迭代法,全过程图解+步步解析,一点点教会你迭代法
    leetcode145.二叉树的后序遍历,递归法+迭代法给你一棵二叉树的根节点root,返回其节点值的后序遍历。示例1:输入:root=[1,null,2,3]输出:[3,2,1]示例2:输入:root=[]输出:[]示例3:输入:root=[1]输出:[1]递归法还是一如既往的简单。postorder函数是递归函数,用......
  • 「代码随想录算法训练营」第十三天 | 二叉树 part3
    110.平衡二叉树题目链接:https://leetcode.cn/problems/balanced-binary-tree/题目难度:简单文章讲解:https://programmercarl.com/0110.平衡二叉树.html视频讲解:https://www.bilibili.com/video/BV1Ug411S7my题目状态:通过思路:采用递归的方式,遍历每个节点的左右孩子的深度......
  • Day 15 二叉树part03
    110.平衡二叉树classSolution{publicbooleanisBalanced(TreeNoderoot){if(root==null)returntrue;returnisBalanced(root.left)&&isBalanced(root.right)&&Math.abs(hight(root.left)-hight(root.right))......
  • 代码随想录算法训练营第14天 | 复习二叉树翻转
    2024年7月17日递归法翻转二叉树易错:要考虑节点为空的情况,以及写好边界条件。/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(){}*TreeNode(intval){this.va......
  • 二叉树 部分定义与性质
    针对于知识回顾/复习,发现一些博客对于一些名词的定义各不相同,于是自己对于部分容易混淆的定义作一个简单的记录。详细关于二叉树的内容可以看:二叉树-Hello算法,部分博客内容来自其中。名词定义1.层层(Level):二叉树中的所有节点可以根据与根节点的距离分成不同的层次。根节点位......