首页 > 编程语言 >代码随想录算法训练营第二十天| 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树

代码随想录算法训练营第二十天| 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树

时间:2023-08-21 14:35:34浏览次数:43  
标签:val t2 t1 搜索 二叉树 二叉 root

 

 654.最大二叉树 

     卡哥建议:又是构造二叉树,昨天大家刚刚做完 中序后序确定二叉树,今天做这个 应该会容易一些, 先看视频,好好体会一下 为什么构造二叉树都是 前序遍历 

    题目链接/文章讲解:https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html

    视频讲解:https://www.bilibili.com/video/BV1MG411G7ox

     做题思路:

     构造树一般采用的是前序遍历,因为先构造中间节点,然后递归构造左子树和右子树。当递归遍历的时候,如果传入的数组大小为1,说明遍历到了叶子节点了。

  1. 先要找到数组中最大的值和对应的下标, 最大的值构造根节点,下标用来下一步分割数组。
  2. 最大值所在的下标左区间 构造左子树
  3. 最大值所在的下标右区间 构造右子树

     每次分隔不用定义新的数组,而是通过下标索引直接在原数组上操作。

    本题代码:

 1 class Solution {
 2 private:
 3     // 在左闭右开区间[left, right),构造二叉树
 4     TreeNode* traversal(vector<int>& nums, int left, int right) {
 5         if (left >= right) return nullptr; //区间要合法
 6 
 7         // 分割点下标:maxValueIndex
 8         int maxValueIndex = left;
 9         for (int i = left + 1; i < right; ++i) {
10             if (nums[i] > nums[maxValueIndex]) maxValueIndex = i;
11         }
12 
13         TreeNode* root = new TreeNode(nums[maxValueIndex]); //中
14 
15         // 左闭右开:[left, maxValueIndex)
16         root->left = traversal(nums, left, maxValueIndex); //左
17 
18         // 左闭右开:[maxValueIndex + 1, right)
19         root->right = traversal(nums, maxValueIndex + 1, right); //右
20 
21         return root;
22     }
23 public:
24     TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
25         return traversal(nums, 0, nums.size()); //传入数组和数组区间
26     }
27 };

 

617.合并二叉树 

    卡哥建议:这次是一起操作两个二叉树了, 估计大家也没一起操作过两个二叉树,也不知道该如何一起操作,可以看视频先理解一下。 优先掌握递归。

    题目链接/文章讲解:https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html

    视频讲解:https://www.bilibili.com/video/BV1m14y1Y7JK

    做题思路:

     两个树的根,左子树,右子树相加,

    因为是传入了两个树,那么就有两个树遍历的节点 t1 和 t2,如果t1 == NULL 了,两个树合并就应该是 t2 了(如果t2也为NULL也无所谓,合并之后就是NULL)。反过来如果 t2 == NULL,那么两个数合并就是 t1(如果t1也为NULL也无所谓,合并之后就是NULL)。

    这里我们重复利用一下t1这个树,t1就是合并之后树的根节点(就是修改了原来树的结构)。

    接下来t1 的左子树是:合并 t1左子树 t2左子树之后的左子树。

    t1 的右子树:是 合并 t1右子树 t2右子树之后的右子树。最终t1就是合并之后的根节点。

    本题代码:

1 TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
2         if (t1 == NULL) return t2; // 如果t1为空,合并之后就应该是t2
3         if (t2 == NULL) return t1; // 如果t2为空,合并之后就应该是t1
4         // 修改了t1的数值和结构
5         t1->val += t2->val;                             // 中
6         t1->left = mergeTrees(t1->left, t2->left);      // 左
7         t1->right = mergeTrees(t1->right, t2->right);   // 右
8         return t1;
9     }

 

 700.二叉搜索树中的搜索 

      卡哥建议:递归和迭代 都可以掌握以下,因为本题比较简单, 了解一下 二叉搜索树的特性

     题目链接/文章讲解: https://programmercarl.com/0700.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%90%9C%E7%B4%A2.html

     视频讲解:https://www.bilibili.com/video/BV1wG411g7sF

      做题思路:

     二叉搜索树是一个有序树:

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  • 它的左、右子树也分别为二叉搜索树

     因为二叉搜索树的节点是有序的,所以可以有方向的去搜索。

     如果root->val > val,搜索左子树,如果root->val < val,就搜索右子树,最后如果都没有搜索到,就返回NULL。

     本题代码:

1 TreeNode* searchBST(TreeNode* root, int val) {
2         if (root == NULL || root->val == val) return root;
3         TreeNode* result = NULL;
4         if (root->val > val) result = searchBST(root->left, val);
5         if (root->val < val) result = searchBST(root->right, val);
6         return result;
7     }

 

98.验证二叉搜索树 

       卡哥建议:遇到搜索树,一定想着中序遍历,这样才能利用上特性。 但本题是有陷阱的,可以自己先做一做,然后在看题解,看看自己是不是掉陷阱里了。这样理解的更深刻。

     题目链接/文章讲解:https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

     视频讲解:https://www.bilibili.com/video/BV18P411n7Q4

     做题思路:

      要知道中序遍历下,输出的二叉搜索树节点的数值是有序序列。有了这个特性,验证二叉搜索树,就相当于变成了判断一个序列是不是递增的了。

    可以递归中序遍历将二叉搜索树转变成一个数组,然后只要比较一下,这个数组是否是有序的,注意二叉搜索树中不能有重复元素。

    关于注意事项看卡哥视频和文章。

     本题代码:

 1 class Solution {
 2 private:
 3     vector<int> vec;
 4     void traversal(TreeNode* root) { //中序遍历
 5         if (root == NULL) return;
 6         traversal(root->left);
 7         vec.push_back(root->val); // 将二叉搜索树转换为有序数组
 8         traversal(root->right);
 9     }
10 public:
11     bool isValidBST(TreeNode* root) {
12         vec.clear(); // 不加这句在leetcode上也可以过,但最好加上
13         traversal(root);
14         for (int i = 1; i < vec.size(); i++) {
15             // 注意要小于等于,搜索树里不能有相同元素
16             if (vec[i] <= vec[i - 1]) return false;
17         }
18         return true;
19     }
20 };

 

 

 

标签:val,t2,t1,搜索,二叉树,二叉,root
From: https://www.cnblogs.com/romantichuaner/p/17637034.html

相关文章

  • 【二叉树前沿篇】树
    1树的概念树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。树有一个特殊的结点,称为根结点,根节点没有前驱结点。除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……......
  • 标签大全(纯文字版) 如需搜索使用Ctrl+F
    【公司信息】全部页面可用公司名称------{co('name')}公司地址------{co('address')}邮政编码------{co('postcode')} 联系人------{co('contact')} 联系手机------{co('phone')} 联系电话------{co('tel')} ......
  • 深入了解Elasticsearch搜索引擎篇:倒排索引、架构设计与优化策略
    什么是倒排索引?有什么好处?倒排索引是一种用于快速检索的数据结构,常用于搜索引擎和数据库中。与传统的正排索引不同,倒排索引是根据关键词来建立索引,而不是根据文档ID。倒排索引的建立过程如下:首先,将每个文档拆分成一系列的关键词或词项,然后建立一个词项到文档的映射。对每个关键......
  • #yyds干货盘点# LeetCode程序员面试金典:完全二叉树的节点个数
    题目:给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。 示例1:输入:r......
  • 验证二叉搜索树
    98.验证二叉搜索树-力扣(LeetCode)二叉搜索树:根节点的左子树的所有元素的值都小于根节点,根节点右子树的所有元素都大于根节点的值。使用中序遍历的序列一定是一个递增的序列,因此一个二叉树如果中序遍历之后得到的是一个递增序列那么它一定是二叉搜索树。 ......
  • 二叉搜索树中的搜索
    700.二叉搜索树中的搜索-力扣(LeetCode)经验1:情况要考虑周全,开始只想到了找到的情况,而没有去想没找到的情况,漏掉了if(root==nullptr)returnroot;经验2:如果该层想要下一层的返回结果,则在该层定义一个返回值类型的变量,然后在该层接递归的返回值......
  • 解密Nginx与Elasticsearch的协同高效:深入理解反向代理与全文搜索
    在当今高度互联的网络环境中,后端技术的结合与优化对于构建高性能应用至关重要。本篇博客将聚焦于两个关键主题:Nginx反向代理和Elasticsearch全文搜索,通过深入分析实现原理和代码示例,展示它们如何协同工作以提升系统性能。Nginx反向代理的作用Nginx不仅仅是一款高性能的Web服务器,还......
  • 深入探索Elasticsearch的分布式搜索与性能优化
    在后端开发领域,Elasticsearch作为一款强大的分布式搜索与分析引擎,被广泛应用于构建高性能的搜索和数据分析系统。本文将深入探讨Elasticsearch的分布式特性、搜索原理以及性能优化策略。通过结合实际代码示例,为读者提供关于Elasticsearch的深奥知识和实用方法。1.Elasticsearch概......
  • 微信小程序(8)搜索页以及历史记录管理
    1.效果1.逻辑界面初始化调接口获取两部分数据:1.搜索框默认的搜索placeholder:下面自由自在...2.热搜榜数据:前20条热搜数据3.获取本地存的历史搜索记录historyList搜索框输入文字事件:1.调用接口根据关键字搜索音乐2.判断搜索记录是否有对应关键字,如果有就将......
  • 【二叉树前沿篇】树
    1树的概念树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。树有一个特殊的结点,称为根结点,根节点没有前驱结点。除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……......