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
思路：DFS
因为我们求的是左叶子节点之和，所以我们要先判断哪个是左叶子节点；
- 题目中的示例2表明只有根节点，虽然也是叶子节点，但不算左叶子节点；
- 所以左叶子节点的条件就是在根节点
root节点左边，且是叶子节点，这样我们就能判断左叶子节点了 - 只需要取出左叶子节点的
val值，累加即可； - 如果不是左叶子节点，则向下递归。
代码：(Java、C++)
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root == null) return 0;
int ans = 0;
if(root.left != null && root.left.left == null && root.left.right == null){
ans = root.left.val;
}else{
ans = sumOfLeftLeaves(root.left);
}
return ans + sumOfLeftLeaves(root.right);
}
}
C++
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root == null) return 0;
int ans = 0;
if(root.left != null && root.left.left == null && root.left.right == null){
ans = root.left.val;
}else{
ans = sumOfLeftLeaves(root.left);
}
return ans + sumOfLeftLeaves(root.right);
}
}
运行结果：
复杂度分析：
- 时间复杂度：
O
(
n
)
O(n)
O(n)，其中
n是树中的节点个数 - 空间复杂度：
O
(
n
)
O(n)
O(n)。空间复杂度与深度优先搜索使用的栈的最大深度相关。在最坏的情况下，树呈现链式结构，深度为
n，对应的空间复杂度也为 O ( n ) O(n) O(n)。
题目来源：力扣。
放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我 leetCode专栏，每日更新！
