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

news/2024/7/3 17:38:55 标签: 算法, leetcode, 职场和发展

目录

一、654. 最大二叉树

二、617. 合并二叉树

 三、700. 二叉搜索树中的搜索

 四、验证二叉搜索树


一、654. 最大二叉树

题目链接:力扣

文章讲解:代码随想录

视频讲解: 又是构造二叉树,又有很多坑!| LeetCode:654.最大二叉树

题目:

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

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

代码:

dfs:

/**
 * 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* creat_tree(vector<int>& nums, int begin, int end){
        if(begin > end) return NULL;
        int target = begin;
        for (int i = begin+1; i <= end; i++)
            if (nums[target] < nums[i]) target = i;
        TreeNode* root = new TreeNode(nums[target]);
        if (begin == end) return root;
        root->left = creat_tree(nums, begin, target-1);
        root->right = creat_tree(nums, target+1, end);
        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return creat_tree(nums, 0, nums.size()-1);
    }
};

单调栈:

/**
 * 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) {
        int size = nums.size();
        vector<TreeNode*> stack;
        for (int i = 0; i < size; i++) {
            TreeNode* node = new TreeNode(nums[i]);
            while (!stack.empty()) {
                TreeNode* topnode = stack.back();
                if (topnode->val > node->val){
                    stack.push_back(node);
                    topnode->right = node;
                    break;
                }
                else{
                    stack.pop_back();
                    node->left = topnode;
                }
            }
            if (stack.empty()) stack.push_back(node);
        }
        return stack[0];
    }
};

时间复杂度: O(n)                                        空间复杂度: O(n)

⏲:35:37

总结:1、递归法类似昨天的通过不同遍历构造其他遍历,都是通过索引来构造新的树。2、单调栈:将题目转换为寻找每个数的左右边界(比这个数大的左右数),然后使用单调栈,保持小进,大出。

二、leetcode.cn/problems/merge-two-binary-trees/" rel="nofollow" title="617. 合并二叉树">617. 合并二叉树

题目链接:力扣

文章讲解:代码随想录

视频讲解:一起操作两个二叉树?有点懵!| LeetCode:617.合并二叉树

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

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

代码:

/**
 * 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) {
        if (root1 == NULL) return root2;
        if (root2 == NULL) return root1;
        root1->val += root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        return root1;
    }
};

时间复杂度: O(n)                                        空间复杂度: O(n)

⏲:1:13

总结:同时操作两棵树。

 三、700. 二叉搜索树中的搜索

题目链接:力扣

文章讲解:代码随想录

视频讲解:不愧是搜索树,这次搜索有方向了!| LeetCode:700.二叉搜索树中的搜索

题目:给定二叉搜索树(BST)的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null 。

代码:

/**
 * 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* searchBST(TreeNode* root, int val) {
        while(root){
            if (root->val == val) return root;
            root = val < root->val ? root->left : root->right;
        }
        return NULL;
    }
};

时间复杂度: O(n)                                        空间复杂度: O(1)

⏲:1:15

总结:  二叉搜索树是一个有序树   (1)若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;(2)若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;(3)它的左、右子树也分别为二叉搜索树(3)二叉搜索树->中序遍历搞定一切问题!!(4)二叉搜索树设置一个pre节点+中序相当于遍历一个有序链表了

            注意不要只简单的以为只是比较root与左右的大小,可能存在,在root右侧,但是比root->left小的数。

 四、验证二叉搜索树

题目链接:力扣

文章讲解:代码随想录

视频讲解:你对二叉搜索树了解的还不够! | LeetCode:98.验证二叉搜索树

题目:给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

代码:

/**
 * 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* pre = NULL;
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        bool left = isValidBST(root->left);
        if (pre && pre->val >= root->val) return false;
        pre = root;
        bool right = isValidBST(root->right);
        return left && right;
    }*/
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> stack;
        TreeNode* pre = NULL;
        while (!stack.empty() || root) {
            if (root){
                stack.push(root);
                root = root->left;
            }
            else{
                root = stack.top();
                stack.pop();
                if (pre && pre->val >= root->val) return false;
                pre = root;
                root = root->right;
            }
        }
        return true;
    }
};

时间复杂度: O(n)                                        空间复杂度: O(n)

⏲:2:49

总结:中序遍历下,输出的二叉搜索树节点的数值是有序序列。


http://www.niftyadmin.cn/n/5422055.html

相关文章

Flink 性能优化总结(内存配置篇)

内存配置优化 Flink 内存模型 内存模型详解 进程内存&#xff08;Total Process Memory&#xff09;&#xff1a;Flink 进程内存分为堆上内存和堆外内存&#xff0c;堆上内存和 堆外内存的主要区别在于它们的管理方式不同和使用方式不同&#xff0c;这些会影响到它们的性能和…

【设计模式】享元模式的使用场景及与其他共享技术的对比

文章目录 1.概述2.享元模式2.1.核心概念2.2.实现案例2.2.1.内部状态实现2.2.2.外部状态实现 2.3.更多场景 3.享元模式的一些对比3.1.与缓存的区别3.2.与池化技术的区别 4.总结 1.概述 享元模式&#xff08;Flyweight Pattern&#xff09;是一种非常常用的结构型设计模式&#…

6.S081的Lab学习——Lab1: Xv6 and Unix utilities

文章目录 前言一、启动xv6(难度&#xff1a;Easy)解析&#xff1a; 二、sleep(难度&#xff1a;Easy)解析&#xff1a; 三、pingpong&#xff08;难度&#xff1a;Easy&#xff09;解析&#xff1a; 四、Primes(素数&#xff0c;难度&#xff1a;Moderate/Hard)解析&#xff1a…

微信小程序云开发教程——墨刀原型工具入门(素材面板)

引言 作为一个小白&#xff0c;小北要怎么在短时间内快速学会微信小程序原型设计&#xff1f; “时间紧&#xff0c;任务重”&#xff0c;这意味着学习时必须把握微信小程序原型设计中的重点、难点&#xff0c;而非面面俱到。 要在短时间内理解、掌握一个工具的使用&#xf…

PostgreSQL教程(三十四):服务器管理(十六)之逻辑复制

逻辑复制是一种基于数据对象的复制标识&#xff08;通常是主键&#xff09;复制数据对象及其更改的方法。我们使用术语“逻辑”来与物理复制加以区分&#xff0c;后者使用准确的块地址以及逐字节的复制方式。PostgreSQL两种机制都支持。逻辑复制允许在数据复制和安全性上更细粒…

14.WEB渗透测试--Kali Linux(二)

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a; 易锦网校会员专享课 上一个内容&#xff1a;13.WEB渗透测试--Kali Linux&#xff08;一&#xff09;-CSDN博客 netcat简介内容:13.WE…

MR混合现实情景实训教学系统模拟高空作业情景

MR混合现实情景实训教学系统&#xff0c;通过精确的三维建模和高动态范围渲染&#xff0c;将真实的高空环境生动地呈现在课堂上。学生可以在虚拟环境中进行模拟操作&#xff0c;如攀爬绳索、悬挂作业等&#xff0c;从而更好地理解和掌握高空作业的技巧和安全规范。同时&#xf…

C#设计原则

学习设计原则是学习设计模式的基础。在实际的开发过程中&#xff0c;并不是一定要求所有的代码都遵循设计原则&#xff0c;而是要综合考虑人力、成本、时间、质量&#xff0c;不刻意追求完美&#xff0c;要在适当的场景遵循设计原则。 这体现的是一种平衡取舍&#xff0c;可以…