左叶子之和

描述

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

示例 1：

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

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

提示:

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sum-of-left-leaves
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

C++代码

这道题可以使用深度优先搜索（DFS）来解决。对于当前节点，如果它的左子节点是叶子节点，那么就把它的左子节点的值加到答案中，否则递归遍历它的左子树。对于右子树，我们递归遍历它的左右子树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (!root) return 0;
        int sum = 0;
        if (root->left && !root->left->left && !root->left->right) { // 当前节点左子节点是叶子节点
            sum += root->left->val;
        } else { // 当前节点左子节点不是叶子节点
            sum += sumOfLeftLeaves(root->left);
        }
        sum += sumOfLeftLeaves(root->right); // 遍历右子树
        return sum;
    }
};

Python代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        sum_ = 0
        if root.left and not root.left.left and not root.left.right:
            sum_ += root.left.val
        else:
            sum_ += self.sumOfLeftLeaves(root.left)
        sum_ += self.sumOfLeftLeaves(root.right)
        return sum_

首先判断当前节点是否为空，如果为空就返回 0。

然后定义一个变量 sum，用来保存左叶子之和。

如果当前节点的左子节点是叶子节点，那么就把它的左子节点的值加到答案中。

否则递归遍历当前节点的左子树。

最后递归遍历当前节点的右子树，把结果加到 sum 中。

最后返回 sum 即可。