110.平衡二叉树 , 257. 二叉树的所有路径 ,404.左叶子之和

简介: 以下是针对这三道二叉树相关问题的简介:本内容涵盖了三道经典的二叉树算法题及其解决方案。第一题“平衡二叉树”通过递归计算左右子树高度差,判断是否为高度平衡二叉树;第二题“二叉树的所有路径”利用深度优先搜索(DFS)遍历树,记录从根节点到叶子节点的所有路径;第三题“左叶子之和”通过递归遍历二叉树,累加所有左叶子节点的值。这些题目帮助理解二叉树的递归与遍历逻辑,适用于算法学习与实践。

题目:110. 平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1:

输入:root = [3,9,20,null,null,15,7]

输出:true

示例 2:

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

输出:false

示例 3:

输入:root = []

输出:true

提示:

树中的节点数在范围 [0, 5000] 内

-104 <= Node.val <= 104

题解:

class Solution {
public:
    // 返回以该节点为根节点的二叉树的高度,如果不是平衡二叉树了则返回-1
    int getHeight(TreeNode* node) {
        if (node == NULL) {
            return 0;
        }
        int leftHeight = getHeight(node->left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;
        return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }
};

题目:257. 二叉树的所有路径

给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1:

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

输出:["1->2->5","1->3"]

示例 2:

输入:root = [1]

输出:["1"]

提示:

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

-100 <= Node.val <= 100

题解:

class Solution {
private:
 
    void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
        path.push_back(cur->val); // 中,中为什么写在这里,因为最后一个节点也要加入到path中  
        // 这才到了叶子节点
        if (cur->left == NULL && cur->right == NULL) {
            string sPath;
            for (int i = 0; i < path.size() - 1; i++) {
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path[path.size() - 1]);
            result.push_back(sPath);
            return;
        }
        if (cur->left) { // 左  
            traversal(cur->left, path, result);
            path.pop_back(); // 回溯
        }
        if (cur->right) { // 右
            traversal(cur->right, path, result);
            path.pop_back(); // 回溯
        }
    }
 
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }
};

题目:404. 左叶子之和

给定二叉树的根节点 root ,返回所有左叶子之和。

示例 1:

输入: root = [3,9,20,null,null,15,7]  

输出: 24  

解释: 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24

示例 2:

输入: root = [1]

输出: 0

提示:

节点数在 [1, 1000] 范围内

-1000 <= Node.val <= 1000

题解:

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right== NULL) return 0;
 
        int leftValue = sumOfLeftLeaves(root->left);    // 左
        if (root->left && !root->left->left && !root->left->right) { // 左子树就是一个左叶子的情况
            leftValue = root->left->val;
        }
        int rightValue = sumOfLeftLeaves(root->right);  // 右
 
        int sum = leftValue + rightValue;               // 中
        return sum;
    }
};
相关文章
|
设计模式 算法 Java
Dating Java8系列之通过行为参数化传递代码
Dating Java8系列之通过行为参数化传递代码
265 0
|
10月前
|
XML 算法 Java
电子税务平台Api接口-发票查验-发票验真-发票核验-发票查验真伪
随着数字化办公和财税电子化管理日益普及,发票的真实性查验已经成为企业财务、税务审计等业务流程中重要的一环。而不符合规定、虚假的发票,不得作为财务凭证,任何企业和个人有权拒收。发票查验接口即可实现发票真实性查验的功能。如对查验结果有疑议,可持发票原件至当地税务机关进行鉴定。
1613 0
|
数据采集 算法 物联网
【算法精讲系列】阿里云百炼SFT微调实践分享
本内容为您提供了百炼平台SFT微调的实践案例,帮助您方便并快速借助模型微调定制化您自己的专属模型。
5005 14
|
算法
平衡二叉树的构建(递归
平衡二叉树的构建(递归
539 0
Latex,WPS公式编辑器,输入花体字母(在mathtype输入花体损失函数L)
Latex,WPS公式编辑器,输入花体字母(在mathtype输入花体损失函数L)
6778 0
|
.NET 程序员 C#
C#对象的销毁和IDisposable
1.对象的析构函数与Finalize方法 与C++类似,C#允许程序员为类定义一个”析构函数“: class MyClass { ~MyClass() //析构函数 { //编写释放非托管的资源 } }  上面的代码编译后,可以看到: 这里调用了Object类的Finalize方法,这个方法里面是空的,什么也没有。
1098 0
|
8天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
9775 25
|
8天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
2756 14
|
3天前
|
人工智能 安全 应用服务中间件
NGINX 爆出两处高危漏洞 可导致未经身份验证的远程代码执行
NGINX曝出两个高危漏洞(CVE-2026-123633和CVE-2026-123007),CVSS 9.2分,均属HTTP/2内存安全缺陷,无需认证即可远程执行代码。影响自2015年起的多个版本,静态站点亦受威胁。修复版本为开源版1.30.7/1.31.9。(239字)
1319 1
NGINX 爆出两处高危漏洞 可导致未经身份验证的远程代码执行
|
6天前
|
传感器 安全 区块链
Windows 电脑运行安卓应用教程:开源工具 ApkStart 双击 APK 即装、独立窗口运行
ApkStart 是一款开源Windows工具,让安卓APP像原生软件一样运行:双击APK即安装、生成真实图标、独立窗口启动、开始菜单可搜索。无需传统模拟器,内置QEMU运行时,支持数据互通、ARM兼容与命令行操作。(239字)