654.最大二叉树 , 617.合并二叉树 , 700.二叉搜索树中的搜索 , 98.验证二叉搜索树

简介: 1. **530. 二叉搜索树的最小绝对差**:通过中序遍历二叉搜索树,计算任意两节点值之间的最小差值。利用递归方法依次比较相邻节点值,更新最小差值。2. **617. 合并二叉树**:将两棵二叉树合并为一棵新树。若两节点重叠,则相加其值;否则保留非空节点。采用递归方式实现,分别处理左右子树。3. **700. 二叉搜索树中的搜索**:在二叉搜索树中查找指定值的节点。利用递归和BST特性(左小右大),高效定位目标节点或返回空。4. **98. 验证二叉搜索树**:判断给定二叉树是否为有效的二叉搜索树。通过中序遍历将树转换为数组,检查数组是否严格递增来验证。

题目:530. 二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数,其数值等于两值之差的绝对值。

示例 1:

输入:root = [4,2,6,1,3]

输出:1

示例 2:

输入:root = [1,0,48,null,null,12,49]

输出:1

提示:

树中节点的数目范围是 [2, 104]

0 <= Node.val <= 105

思考过程与知识点:

构造树一般采用的是前序遍历,因为先构造中间节点,然后递归构造左子树和右子树。

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

参数传入的是存放元素的数组,返回该数组构造的二叉树的头结点,返回类型是指向节点的指针。

确定终止条件

题目中说了输入的数组大小一定是大于等于1的,所以我们不用考虑小于1的情况,那么当递归遍历的时候,如果传入的数组大小为1,说明遍历到了叶子节点了。

那么应该定义一个新的节点,并把这个数组的数值赋给新的节点,然后返回这个节点。 这表示一个数组大小是1的时候,构造了一个新的节点,并返回。

题解:

class Solution {
private:
int result = INT_MAX;
TreeNode* pre = NULL;
void traversal(TreeNode* cur) {
    if (cur == NULL) return;
    traversal(cur->left);   // 左
    if (pre != NULL){       // 中
        result = min(result, cur->val - pre->val);
    }
    pre = cur; // 记录前一个
    traversal(cur->right);  // 右
}
public:
    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        return result;
    }
};

题目: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

思考历程与知识点:

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

首先要合入两个二叉树,那么参数至少是要传入两个二叉树的根节点,返回值就是合并之后二叉树的根节点。

     2.确定终止条件:

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

反过来如果t2 == NULL,那么两个数合并就是t1(如果t1也为NULL也无所谓,合并之后就是NULL)。

题解:

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        // 重新定义新的节点,不修改原有两个树的结构
        TreeNode* root = new TreeNode(0);
        root->val = t1->val + t2->val;
        root->left = mergeTrees(t1->left, t2->left);
        root->right = mergeTrees(t1->right, t2->right);
        return root;
    }
};

题目:700. 二叉搜索树中的搜索

给定二叉搜索树(BST)的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null 。

示例 1:

输入:root = [4,2,7,1,3], val = 2

输出:[2,1,3]

示例 2:

输入:root = [4,2,7,1,3], val = 5

输出:[]

提示:

数中节点数在 [1, 5000] 范围内

1 <= Node.val <= 107

root 是二叉搜索树

1 <= val <= 107

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

递归函数的参数传入的就是根节点和要搜索的数值,返回的就是以这个搜索数值所在的节点。

确定终止条件

如果root为空,或者找到这个数值了,就返回root节点。

确定单层递归的逻辑

看看二叉搜索树的单层递归逻辑有何不同。

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

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

题解:

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == NULL || root->val == val) return root;
        TreeNode* result = NULL;
        if (root->val > val) result = searchBST(root->left, val);
        if (root->val < val) result = searchBST(root->right, val);
        return result;
    }
};

题目:98. 验证二叉搜索树

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

节点的左子树只包含 小于 当前节点的数。

节点的右子树只包含 大于 当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:root = [2,1,3]

输出:true

示例 2:

输入:root = [5,1,4,null,null,3,6]

输出:false

解释:根节点的值是 5 ,但是右子节点的值是 4 。

提示:

树中节点数目范围在[1, 104] 内

-231 <= Node.val <= 231 - 1

题解:

class Solution {
private:
    vector<int> vec;
    void traversal(TreeNode* root) {
        if (root == NULL) return;
        traversal(root->left);
        vec.push_back(root->val); // 将二叉搜索树转换为有序数组
        traversal(root->right);
    }
public:
    bool isValidBST(TreeNode* root) {
        vec.clear(); // 不加这句在leetcode上也可以过,但最好加上
        traversal(root);
        for (int i = 1; i < vec.size(); i++) {
            // 注意要小于等于,搜索树里不能有相同元素
            if (vec[i] <= vec[i - 1]) return false;
        }
        return true;
    }
};
相关文章
|
数据库 索引
评论功能里数据库的设计
【4月更文挑战第2天】本文探讨了评论系统的树形结构设计,提出了四种方法:邻接表、分段式path、Nested Set和Closure Table。针对评论业务功能,如加载评论页和查看回复,优先考虑邻接表和分段式path。采用邻接表思路,设计了评论表结构,包括Uid、Biz、BizID、RootID、PID、Content、索引和级联删除规则。同时提到了索引设计,如Uid、Biz+BizID、PID和Ctime/Utime,以优化查询性能。
710 3
|
SQL 分布式计算 Java
Hive教程(07)- Hive自定义用户名密码验证(已开源)
Hive教程(07)- Hive自定义用户名密码验证(已开源)
1112 0
|
2月前
|
人工智能 前端开发 NoSQL
又一个 AI 新项目完结,用 DeepSeek 搞了个 PPT 生成器!
手把手带你用 AI 编程做出一个能上线传播、能变现的 AI 智能 PPT 制作工具产品!最新 AI Agent 应用开发 + Vibe Coding 项目,基于 Python FastAPI + LangChain + LangGraph + React 开发,秋招简历亮点拉满~
338 3
|
3月前
|
人工智能 安全 API
最新版通义千问(Qwen3.8-Max)功能介绍
在人工智能大模型技术快速迭代的当下,通义千问推出的Qwen3.8-Max凭借突破性的技术架构与全面升级的能力,成为大模型领域的全新标杆。作为通义千问系列迄今规模最大、能力最强的旗舰模型,Qwen3.8-Max以2.4万亿总参数的体量,结合前沿稀疏混合专家(MoE)架构,在保持高效推理的同时,实现了文本理解、代码生成、多模态交互、长周期任务执行等核心能力的跨越式提升,为个人用户、开发者与企业级应用提供了前所未有的AI能力支撑。
940 1
|
5月前
|
人工智能 运维 Linux
AI Agent进阶:从OpenClaw迁移至Hermes Agent全教程:安装、配置与实战及避坑指南
在AI智能体快速迭代的2026年,各类开源Agent框架逐步从基础工具调用向自进化、长效运行方向升级。OpenClaw作为早期热门AI智能体,凭借稳定的网关架构、丰富的插件生态收获大量用户,而同生态的**Hermes Agent**凭借独有的自进化学习闭环、分层记忆系统、更高的运行透明度,成为新一代优选框架。不少原有OpenClaw用户希望平滑迁移至Hermes Agent,同时保留历史配置、记忆内容与自定义技能。本文结合官方文档与实测经验,全面讲解两款框架的核心架构差异、前置调研要点、完整安装步骤、一键迁移流程、配置调试、多场景实战以及常见问题排查,全程兼顾零基础使用者与专业开发者,帮助用户
544 0
|
人工智能 安全 数据可视化
配置驱动的动态Agent架构网络:实现高效编排、动态更新与智能治理
本文系统性地提出并阐述了一种配置驱动的独立运行时Agent架构,旨在解决当前低代码/平台化Agent方案在企业级落地时面临困难,为Agent开发领域提供了一套通用的、可落地的标准化范式。
906 18
配置驱动的动态Agent架构网络:实现高效编排、动态更新与智能治理
|
8月前
|
人工智能 安全 Linux
零基础保姆级|阿里云计算巢秒级部署+本地搭建OpenClaw,无缝对接千问/Qwen3-Max与免费Coding Plan API
本文详细拆解了阿里云计算巢与本地多系统(Windows11/macOS/Linux)的部署流程,提供了可直接复制执行的代码命令,覆盖部署前准备、核心步骤、千问/Coding Plan API配置、技能扩展、问题排查等全场景,全程无营销词汇,不提及无关平台,确保新手能快速上手。需要注意的是,大模型API Key的安全管理、服务器端口的合理配置、技能的精准选型(优先安装安全技能)、模型参数的优化,是保障OpenClaw与大模型稳定运行、发挥最大价值的关键。
1279 0
|
11月前
|
监控 网络协议 Linux
实用程序:Python打造进程网络监控与分析工具——全方位掌握你的网络与进程状态
一款基于Python开发的进程网络监控与分析工具,支持实时监控进程带宽、端口占用、网络环境信息及诊断功能,内置网速测试、Ping、路由追踪等实用工具,提供直观UI界面,操作简单。数据可导出为CSV或图表,便于分析。开源免费,Windows为主,兼容Linux/macOS。GitHub已开源,欢迎Star!
564 0
|
弹性计算 tengine 负载均衡
slb高可用性
【11月更文挑战第4天】
667 1