【力扣题解】P404-左叶子之和-Java题解

👨‍💻博客主页：@花无缺
欢迎 点赞👍 收藏⭐ 留言📝 加关注✅!
本文由 花无缺 原创

收录于专栏 【力扣题解】

---

---

【力扣题解】P404-左叶子之和-Java题解

P404.左叶子之和

🌏题目描述

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

示例 1：

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

示例 2:

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

提示:

• 节点数在 [1, 1000] 范围内
• -1000 <= Node.val <= 1000

💡题解

深度优先搜索：

public int sumOfLeftLeaves(TreeNode root) {return root == null ? 0 : dfs(root);
}
// 深度优先搜索
public static int dfs(TreeNode node) {int res = 0;// 递归搜索左子树if (node.left != null) {// 如果当前左子树是叶子节点就累加节点值// 如果不是叶子节点就继续递归遍历该节点res += isLeafNode(node.left) ? node.left.val : dfs(node.left);}// 递归搜索右子树// 如果当前右子树不是叶子节点就递归遍历右子树if (node.right != null && !isLeafNode(node.right)) {res += dfs(node.right);}return res;
}
// 判断节点是否是叶子节点
// 如果当前节点的左右子树都为空, 那么该节点就是叶子节点
public static boolean isLeafNode(TreeNode node) {return node.left == null && node.right == null;
}

广度优先搜索：

public int sumOfLeftLeaves(TreeNode root) {// 空树if (root == null) {return 0;}int res = 0;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int len = queue.size();while (len-- > 0) {TreeNode node = queue.poll();// 左子树不为空if (node.left != null) {// 左子树是叶子节点, 则累加节点值if (isLeafNode(node.left)) {res += node.left.val;//     不是叶子节点, 将节点加入队列} else {queue.offer(node.left);}}// 右子树不空if (node.right != null) {// 右子树不是叶子节点, 将节点加入队列if (!isLeafNode(node.right)) {queue.offer(node.right);}}}}return res;
}

时间复杂度：均为O(n)，树的所有节点都要遍历一次，节点数为 n。

🌏总结

这个题的解题思路：遍历 + 判断。

• 遍历：遍历二叉树的所有节点
• 判断：判断当前节点是否是左子节点，以及是否是叶子节点

只要一个节点满足判断中的两个条件，那么我们就可以将当前节点的节点值累加起来，如果当前节点是右子节点或者不是叶子节点，那么我们就继续递归的遍历它，就可以得到最终的答案。

作者：花无缺(huawuque404.com)

---

🌸欢迎关注我的博客：花无缺-每一个不曾起舞的日子都是对生命的辜负~
🍻一起进步-刷题专栏：【力扣题解】
🥇往期精彩好文：
📢【CSS选择器全解指南】
📢【HTML万字详解】
你们的点赞👍 收藏⭐ 留言📝 关注✅
是我持续创作，输出优质内容的最大动力！
谢谢！