18_左叶子之和

简介: 18_左叶子之和

左叶子之和

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

示例 1:

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24

示例 2:

输入: root = [1]
输出: 0

【思路】

首先要注意是判断左叶子,不是二叉树左侧节点,所以无法使用层序遍历。

左叶子的明确定义:节点A的左孩子不为空,且做孩子的左右孩子都为空,且做孩子的左右孩子都为空(说明是叶子结点),那么A节点的做孩子为左叶子节点,那么A的左孩子为左叶子节点。

判断当前节点是不是左叶子是无法判断的,必须要通过节点的父节点来判断其左孩子是不是左叶子。如果该节点的左节点不为空,该节点的左节点的左节点为空,该节点的左节点的右节点为空,则找到了一个左叶子,代码判断如下:

if (node.left != null && node.left.left == null && node.left,right == null) {
  // 左叶子节点处理逻辑
}

递归法

递归的遍历顺序为后序遍历(左右中),是因为要通过递归函数的返回值来累加求取左叶子数值之和。

递归三部曲:

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

判断一个树的左叶子节点之和,那么一定要传入树的根节点,递归函数的返回值为数值之和,所以为int

2、确定递归终止条件

如果遍历到空节点,那么左叶子值一定是0

if (root == null)  return 0;

注意:只有当前遍历的节点是父节点,才能判断其子节点是不是左叶子。所以如果当前遍历的节点是叶子结点,那么其左叶子也必定是0,那么终止条件为:

if (root == null)   return 0;
if (root.left == null && root.right == null)  return 0;//其实这个也可以不写,如果不写不影响结果,但就会让递归多进行了一层。

3、确定单层递归的逻辑

当遇到左叶子节点的时候,记录数值。然后通过递归求取左子树左叶子之和和右子树左叶子之和,相加便是整个树的左叶子之和。

int leftValue = sumOfLeftLeaves(root.left);  //左
if (root.left && !root.left.left && !root.left.right) {
  leftValue = root.left.val;
}
int right = sumOfLeftLeaves(root.right);  //右
int sum = leftValue + rightValue;  //中
return sum;

简化版本:

class Solution {
  public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        int leftValue = sumOfLeftLeaves(root.left);    // 左
        int rightValue = sumOfLeftLeaves(root.right);  // 右
                                                       
        int midValue = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) { 
            midValue = root.left.val;
        }
        int sum = midValue + leftValue + rightValue;  // 中
        return sum;
    }
}

迭代法

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        Stack<TreeNode> stack = new Stack<> ();
        stack.add(root);
        int result = 0;
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.left != null && node.left.left == null && node.left.right == null) {
                result += node.left.val;
            }
            if (node.right != null) stack.add(node.right);
            if (node.left != null) stack.add(node.left);
        }
        return result;
    }
}
JAVA 复制 全屏

总结

这道题目要求左叶子之和,其实是比较绕的,因为不能判断本节点是不是左叶子节点。

此时就要通过节点的父节点来判断其左孩子是不是左叶子了。

平时我们解二叉树的题目时,已经习惯了通过节点的左右孩子判断本节点的属性,而本题我们要通过节点的父节点判断本节点的属性。

希望通过这道题目,可以扩展大家对二叉树的解题思路。

相关文章
|
Web App开发 数据中心 Windows
【镜像更新】Windows Server 2012 R2 数据中心版
信息摘要: Windows Server 2012 R2 数据中心版镜像更新适用客户: 使用Windows Server 2012 R2的用户版本/规格功能: 镜像ID: win2012r2_64_dtc_9600_zh-cn_40G_alibase_20190318.
6705 0
|
10月前
|
监控 安全 机器人
钓鱼团伙用Telegram机器人“接单”:欧洲凭证窃取进入“实时客服”时代
2025年,一种以Telegram机器人为核心的新型钓鱼攻击在欧洲蔓延。攻击者利用开放API构建“钓鱼SaaS”,实现凭证捕获、实时交互与会话劫持全自动化。数据显示,此类攻击同比增长320%,传统防御难以应对。专家呼吁升级多因素认证、封禁高风险通道,并强化行为监测,防范“人机协同”式网络钓鱼威胁。
893 8
|
11月前
|
内存技术
观海微电子---常用电子元器件_磁珠
磁珠是一种铁氧体材料制成的高频噪声抑制器件,等效为电阻与电感串联,具有高阻抗特性。其单位为欧姆(Ω),在低频时呈感性,反射噪声;高频时呈阻性,吸收噪声并转化为热能,常用于RF电路、高速信号线等EMI防护,区别于储能用的电感,专用于滤除高频干扰。
|
11月前
|
人工智能 API
阿里云获评Omdia全球企业级MaaS市场领导者,5项关键能力获最高评级
2025年12月,国际市场研究机构 Omdia 发布最新报告《2025年全球企业级MaaS市场分析》(以下简称“报告”),提出9项评估维度。阿里云获评全球领导者,并在5大维度上获得最高评级,为国内评价最佳的厂商;在国际上仅次于AWS,与Azure、谷歌云持平。
|
11月前
|
索引
如何对局部敏感哈希值进行相似检索?
利用SimHash与海明距离可判断文档相似性。为提升检索效率,Google采用抽屉原理:将64位哈希值均分4段,若两值海明距离≤3,则至少有一段完全相同。据此建立4个倒排索引,每段16位作键,查询时仅需匹配同段相同的文档,大幅缩小范围,实现海量数据下高效去重。
|
消息中间件 算法 Linux
【Linux】详解如何利用共享内存实现进程间通信
【Linux】详解如何利用共享内存实现进程间通信
1583 1
|
SQL 监控 Oracle
Oracle 亿级数据 更新 实战方案
本文介绍在10亿级数据表中高效更新1亿条数据的完整方案,涵盖环境评估、策略选择、分阶段实施、RAC环境优化、监控容灾及性能调优等内容,结合并行DML、分区交换等技术,保障大规模数据更新的稳定性与效率。
|
数据采集 人工智能 调度
传统IT企业如何在AI时代中找准定位、实现转型升级?—— 解析传统IT企业的AI转型策略
本文AI专家三桥君探讨传统IT企业在AI浪潮中的转型策略,提出从工具提供商向业务成果交付者的商业模式转变。核心观点包括:构建"操作系统式AI"技术架构、发展"智能体经济"组织模式、采用SMART策略实现高效部署。三桥君强调AI转型需商业模式、组织架构与技术体系的全面革新,为传统IT企业提供系统性转型框架。
895 0
|
XML 数据可视化 Java
文本对比工具,绕不开这个6款!
文本对比工具,绕不开这个6款!
2906 0
|
存储 人工智能 算法
云工开物合作动态丨阿里云人工智能通识教学合作
阿里云人工智能通识教学合作为高校提供全面支持,包括视频理论课、动手实践课、AI实践平台、教学管理平台、专属算力资源及线下workshop。