树与图简单2 种解法

#404左叶子之和

计算二叉树中所有左叶子节点值的总和。

#二叉树#深度优先搜索#广度优先搜索

解题主线

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

解法 1：递归判断左孩子

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

时间复杂度

O(n)

空间复杂度

O(h)

404. 左叶子之和 · 递归判断左孩子

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)

404. 左叶子之和 · BFS 累加

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