( “树” 之 DFS) 404. 左叶子之和 ——【Leetcode每日一题】

小鱼儿 2024-03-23 12:31 43阅读 0赞

### 404. 左叶子之和 ###

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

##### 示例 1： #####

![在这里插入图片描述][c835becbcc0e4d7ab019bd0f87def715.png]

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

##### 示例 2: #####

![在这里插入图片描述][8e7b90309a8944639da7ea5e7a1eaa54.png]

> 输入: 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++**

##### 运行结果： #####

![在这里插入图片描述][f0615e3ce8e348489fc2f5e9f103d289.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ) O(n) O(n)，其中 `n` 是树中的节点个数
 *  **空间复杂度**： O ( n ) O(n) O(n)。空间复杂度与深度优先搜索使用的栈的最大深度相关。在最坏的情况下，树呈现链式结构，深度为 `n` ，对应的空间复杂度也为  O ( n ) O(n) O(n)。

题目来源：[力扣。][Link 1]

> 放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！  
> 关注我 [leetCode专栏][leetCode]，每日更新！

##### 注： 如有不足，欢迎指正！ #####

[c835becbcc0e4d7ab019bd0f87def715.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/d359a149a67144b2bb61c42ccadf5f82.png
[8e7b90309a8944639da7ea5e7a1eaa54.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/8cf22fe606784e278de3090a001b6cee.png
[f0615e3ce8e348489fc2f5e9f103d289.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/c876749fbfac4558a86e7773c0e6611d.png
[Link 1]: https://leetcode.cn/problems/sum-of-left-leaves/description/
[leetCode]: http://t.csdn.cn/kQLJO