树与图简单2 种解法

#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

查看原题

解题主线

判断左叶子要站在其父节点观察：左孩子非空且没有孩子。

解法 1：递归判断左孩子

当前节点负责贡献自己的左叶子，再递归统计两棵子树。

时间复杂度： O(n)
空间复杂度： O(h)

JAVA

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        // 只有父节点的左孩子同时为叶子时，才把该值计入答案。
        // 根节点自身即使是叶子也没有“左孩子”身份，因此不贡献。
        if (root == null) return 0;
        int contribution = isLeaf(root.left) ? root.left.val : 0;
        return contribution + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }

    private boolean isLeaf(TreeNode node) {
        return node != null && node.left == null && node.right == null;
    }
}

解法 2：BFS 累加

遍历每个父节点，发现左叶子时累加。

时间复杂度： O(n)
空间复杂度： O(w)

JAVA

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        // 只有父节点的左孩子同时为叶子时，才把该值计入答案。
        // 根节点自身即使是叶子也没有“左孩子”身份，因此不贡献。
        if (root == null) return 0;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int sum = 0;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                if (node.left.left == null && node.left.right == null) sum += node.left.val;
                else queue.offer(node.left);
            }
            if (node.right != null) queue.offer(node.right);
        }
        return sum;
    }
}

边界与易错点

左孩子不等于左叶子；其必须同时没有左右孩子。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/tree/Q404_sumOfLeftLeaves.java