404.左叶子之和

力扣题目链接(opens new window)

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

示例：

算法公开课

《代码随想录》算法视频公开课 (opens new window)：：二叉树的题目中，总有一些规则让你找不到北 | LeetCode：404.左叶子之和 (opens new window)，相信结合视频在看本篇题解，更有助于大家对本题的理解。

#思路

首先要注意是判断左叶子，不是二叉树左侧节点，所以不要上来想着层序遍历。

因为题目中其实没有说清楚左叶子究竟是什么节点，那么我来给出左叶子的明确定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点

大家思考一下如下图中二叉树，左叶子之和究竟是多少？

 其实是0，因为这棵树根本没有左叶子！

但看这个图的左叶子之和是多少？

相信通过这两个图，大家对最左叶子的定义有明确理解了。

那么判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。

如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子，判断代码如下：

if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
    左叶子节点处理逻辑
}

/**
 * 404. 左叶子之和 (Sum of Left Leaves)
 * 
 * 题目描述：
 * 给定一个二叉树的根节点 root，返回所有左叶子节点的值之和。
 * 左叶子：指的是一个叶子节点（没有左右子节点），并且它是其父节点的左子节点。
 * 
 * 示例：
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 在这个树中，只有节点 9 和 15 是叶子节点。其中：
 * - 节点 9 是根节点 3 的左子节点，且是叶子 → 是左叶子
 * - 节点 15 是节点 20 的左子节点，且是叶子 → 是左叶子
 * 所以返回 9 + 15 = 24。
 */

class Solution {
    /**
     * 使用层序遍历（BFS）的方式计算二叉树中所有左叶子节点的值之和。
     * 
     * @param root 二叉树的根节点
     * @return 所有左叶子节点值的总和
     */
    public int sumOfLeftLeaves(TreeNode root) {
        // 如果根节点为空，直接返回 0
        if (root == null) return 0;

        // 使用双端队列（Deque）来实现层序遍历（广度优先搜索）
        // LinkedList 实现了 Deque 接口，适合做队列使用
        Deque<TreeNode> deque = new LinkedList<>();
        
        // 将根节点入队，作为遍历的起点
        deque.offer(root);

        // 初始化左叶子节点值的总和为 0
        int sum = 0;

        // 当队列不为空时，继续遍历
        while (!deque.isEmpty()) {
            // 获取当前层的节点数量，用于分层处理（虽然本题不需要严格分层，但保留了结构）
            int len = deque.size();

            // 遍历当前层的所有节点
            while (len-- > 0) {
                // 出队一个节点
                TreeNode node = deque.poll();

                // 判断该节点的左子节点是否为“左叶子”
                // 条件：
                // 1. 存在左子节点：node.left != null
                // 2. 左子节点是叶子节点：node.left.left == null && node.left.right == null
                if (node.left != null && node.left.left == null && node.left.right == null) {
                    // 如果满足条件，则将该左叶子的值加入总和
                    sum += node.left.val;
                }

                // 将当前节点的左子节点入队（即使它是叶子也要入队，因为需要访问它来判断其兄弟或父关系）
                if (node.left != null) {
                    deque.offer(node.left);
                }

                // 将当前节点的右子节点入队
                if (node.right != null) {
                    deque.offer(node.right);
                }
            }
            // 注意：这里的内层 while 循环虽然实现了按层遍历，
            // 但对于本题来说，并不需要区分层级，可以直接用 while(!deque.isEmpty()) { ... }
            // 所以这个 len 控制是多余的，但不影响正确性。
        }

        // 返回最终的左叶子之和
        return sum;
    }
}