首页 > 编程语言 >代码随想录算法训练营第十七天(一)| 654.最大二叉树 617.合并二叉树

代码随想录算法训练营第十七天(一)| 654.最大二叉树 617.合并二叉树

时间:2024-08-16 22:52:32浏览次数:12  
标签:right TreeNode nums 随想录 654 二叉树 root1 节点 left

654.最大二叉树

题目:

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

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

返回 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. 递归构建左右子树:

    • 通过将数组分为两部分来递归地构建左子树和右子树。
    • 左子树由最大值左边的子数组构成,右子树由最大值右边的子数组构成。

上代码:

/**
 * 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) {
        return construct(nums, 0, nums.size() - 1);
    }
    
private:
    TreeNode* construct(const vector<int>& nums, int left, int right) {
        // 范围无效,返回 nullptr
        if (left > right) return nullptr;

        // 步骤 1: 找到当前范围 [left, right] 中最大值的索引
        int maxIndex = left;
        for (int i = left; i <= right; ++i) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }

        // 步骤 2: 使用找到的最大值创建新的 TreeNode 节点
        TreeNode* root = new TreeNode(nums[maxIndex]);

        // 步骤 3: 递归地构建左子树和右子树
        // 左子树由范围 [left, maxIndex - 1] 构建
        root->left = construct(nums, left, maxIndex - 1);
        // 右子树由范围 [maxIndex + 1, right] 构建
        root->right = construct(nums, maxIndex + 1, right);

        return root;
    }

};

617.合并二叉树

题目:

给你两棵二叉树: root1 和 root2 。

想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1:

输入:root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出:[3,4,5,5,4,null,7]

示例 2:

输入:root1 = [1], root2 = [1,2]
输出:[2,2]

提示:

  • 两棵树中的节点数目在范围 [0, 2000] 内
  • -104 <= Node.val <= 104

思路:

  • 检查节点是否为空:如果 root1root2 为空,那么直接返回另一个非空的节点作为合并后的节点。

  • 合并当前节点:如果两个节点都不为空,那么我们将这两个节点的值相加,并且递归地合并它们的左子树和右子树。

  • 递归合并子树:我们将合并后的结果赋值给当前节点,并递归处理左右子树。

上代码:

/**
 * 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* mergeTrees(TreeNode* root1, TreeNode* root2) {
        // 如果 root1 为空,则返回 root2
        if (!root1) return root2;
        // 如果 root2 为空,则返回 root1
        if (!root2) return root1;
        
        // 合并当前节点的值
        root1->val += root2->val;
        
        // 递归合并左右子树
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        
        // 返回合并后的树根节点
        return root1;
    }
    
};

标签:right,TreeNode,nums,随想录,654,二叉树,root1,节点,left
From: https://blog.csdn.net/xiaowutongxue666/article/details/141270959

相关文章

  • 代码随想录算法训练营第十七天(二)| 700.二叉搜索树中的搜索 98.验证二叉搜索树
    700.二叉搜索树中的搜索题目:给定二叉搜索树(BST)的根节点 root 和一个整数值 val。你需要在BST中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在,则返回 null 。示例1:输入:root=[4,2,7,1,3],val=2输出:[2,1,3]示例2:输入:roo......
  • 二叉树的递归与非递归遍历:C++实现
    在数据结构的学习中,二叉树是一个非常重要的概念。遍历二叉树是理解和操作二叉树的基础。本文将介绍如何使用C++实现二叉树的递归和非递归遍历,包括前序、中序和后序遍历,并对每种遍历方法的原理进行简要介绍。二叉树节点定义首先,我们定义一个简单的二叉树节点结构:structTreeN......
  • 随想录day3:203.移除链表元素|707.设计链表 |206.反转链表
    203.移除链表元素方法一:直接遍历,永远记得处理head,删除链表必须有前驱。/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(){}*ListNode(intval){this.val=val;}*ListNode......
  • 【代码随想录】二、链表:2、设计链表
    部分图文参考于:代码随想录-707.设计链表。这道题目设计链表的五个接口:●获取链表第index个节点的数值●在链表的最前面插入一个节点●在链表的最后面插入一个节点●在链表第index个节点前面插入一个节点●删除链表的第index个节点可以说这五个接口,已经覆盖了链表的......
  • 【代码随想录】二、链表:1、移除链表元素
    部分图文参考于:代码随想录-203.移除链表元素。C++编程中记得要手动释放结点内存。链表操作中,可以使用原链表来直接进行删除操作,也可以设置一个虚拟头结点再进行删除操作。1.题目链接203.移除链表元素2.思路以链表1424来举例,移除元素4。如果使用C,C++编程语言的话,......
  • 【代码随想录】二、链表:理论基础
    原文链接:代码随想录-链表理论基础。1.什么是链表?链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。链表的入口节点称为链表的头结点也就是head。2.链表的类型2.1.......
  • 代码随想录 day31|| 56 合并区间,738 单调递增数字,968 监控二叉树
    56合并区间funcmerge(intervals[][]int)[][]int{ //思路先排序,然后按照后一个左区间和前一个右区间进行对比判断是否重叠,重叠扩充右区间 sort.Slice(intervals,func(i,jint)bool{ ifintervals[i][0]==intervals[j][0]{ returnintervals[i][1]<intervals[......
  • 「代码随想录算法训练营」第三十九天 | 动态规划 part12
    115.不同的子序列题目链接:https://leetcode.cn/problems/distinct-subsequences/文章讲解:https://programmercarl.com/0115.不同的子序列.html题目难度:困难视频讲解:https://www.bilibili.com/video/BV1fG4y1m75Q/题目状态:看题解思路:动态规划数组初始化创建一个二维动......
  • 【数据结构】关于树(二叉树)的基础理论知识,你知道吗???
    前言:......
  • 代码随想录Day16
    513.找树左下角的值给定一个二叉树的根节点root,请找出该二叉树的最底层最左边节点的值。假设二叉树中至少有一个节点。示例1:输入:root=[2,1,3]输出:1示例2:输入:[1,2,3,4,null,5,6,null,null,7]输出:7提示:二叉树的节点个数的范围是[1,104]-231<=......