Leetcode 404.左叶子之和

力扣传送门(opens new window)

计算给定二叉树的所有左叶子之和。

示例 1：

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

示例 2:

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

解题思路：

要计算二叉树中所有左叶子的和，可以使用深度优先搜索（DFS）的方法来解决。具体思路如下：

1. 定义一个辅助函数 dfs，该函数用于进行深度优先搜索，并累加左叶子节点的值。
2. 在 dfs 函数中，首先进行一个判断，如果当前节点为空，即到达了空节点，那么返回0。
3. 如果当前节点的左子节点不为空，且左子节点是叶子节点（即没有左右子节点），那么将左子节点的值累加到结果中。
4. 递归调用 dfs 函数，分别处理左子树和右子树，并将结果累加到结果中。
5. 编写主函数 sumOfLeftLeaves，用于调用 dfs 函数并返回最终的结果。
6. 在主函数中，首先进行一个判断，如果根节点为空，即整棵树为空树，那么返回0。
7. 如果根节点不为空，那么调用 dfs 函数，并将结果返回作为最终的答案。

通过深度优先搜索，可以遍历二叉树中的所有节点，判断并累加左叶子节点的值，最终返回左叶子节点的和作为答案。

代码实现：

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            // 如果根节点为空，返回0
            return 0; 
        }
         // 调用深度优先搜索函数并返回结果
        return dfs(root);
    }

    private int dfs(TreeNode node) {
        int sum = 0;
        // 如果当前节点的左子节点不为空且为叶子节点，将左子节点的值累加到结果中
        if (node.left != null && node.left.left == null && node.left.right == null) {
            sum += node.left.val;
        }
        // 递归处理左子树和右子树，并将结果累加到结果中
        if (node.left != null) {
            sum += dfs(node.left);
        }
        if (node.right != null) {
            sum += dfs(node.right);
        }
        return sum; 
    }
}