难度: Easy
给定二叉树的根节点 root ，返回所有左叶子之和。
示例 1：
输入: root = [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
示例 2:
输入: root = [1] 输出: 0
提示:
- 节点数在
[1, 1000]范围内 -1000 <= Node.val <= 1000
Submission
运行时间: 40 ms
内存: 15.2 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
class Solution:
def sumOfLeftLeaves(self, root: TreeNode) -> int:
if root is None:
return 0
q = deque()
q.append((root, False))
s = 0
while q:
size = len(q)
for _ in range(size):
node, is_left = q.popleft()
if node:
if is_left and node.left is None and node.right is None:
s += node.val
q.append((node.left, True))
q.append((node.right, False))
return s
Explain
这个题解使用广度优先搜索（BFS）的方法来遍历二叉树。它维护一个队列，将每个节点和一个布尔值（表示该节点是否为左子节点）作为元组放入队列中。在BFS的过程中，如果遇到一个节点是左叶子（即它是左子节点且没有左右子节点），就将它的值累加到变量s中。最后返回s作为所有左叶子之和。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
class Solution:
def sumOfLeftLeaves(self, root: TreeNode) -> int:
if root is None:
return 0
q = deque()
q.append((root, False)) # 根节点不是左节点，初始为False
s = 0
while q:
size = len(q)
for _ in range(size):
node, is_left = q.popleft()
if node:
# 如果当前节点是左叶子，累加它的值
if is_left and node.left is None and node.right is None:
s += node.val
# 左子节点入队，并标记为左节点
q.append((node.left, True))
# 右子节点入队，并标记为非左节点
q.append((node.right, False))
return s
Explore
在许多情况下，BFS和DFS都可以用来解决同样的问题，但是BFS的特点是按层次遍历树结构，这使得它在处理问题时更为直观和结构化。在此题中，使用BFS可以方便地一层层处理各个节点，并且通过维护一个队列来实现迭代而非递归，有时可以避免深度递归导致栈溢出的问题。此外，BFS的这种按层次的处理逻辑有助于清晰地区分节点是左子节点还是右子节点，便于实现题目要求的判断左叶子节点的逻辑。
题解中的布尔值用于标记队列中的节点是否为左子节点。这个标记对于判断一个节点是否是左叶子至关重要，因为左叶子的定义不仅要求此节点无子节点，还必须是其父节点的左子节点。因此，布尔值在算法中的角色是帮助确认节点是否满足左叶子的条件，即它既是左子节点，又没有子节点。
在BFS中，通常会将所有子节点加入队列，包括null节点，这是为了保持队列的完整性和一致性，特别是在需要层级信息时。然而，在此题解中，其实可以优化以避免将null节点入队。将null节点加入队列并不会对结果产生影响，但会增加不必要的空间使用和检查次数。应该在将子节点入队前检查其是否为null，若为null则跳过，这样可以提高效率。
题解的算法逻辑中并没有特别处理节点值为负数的情况，因为它直接对满足左叶子条件的节点的值进行累加。如果树中存在值为负数的左叶子节点，这些节点的值会被加入总和中，从而减少总和的值。因此，如果左叶子节点的值包含负数，这将直接影响求和结果，使总和减小。这在处理实际问题时应当注意，确保结果的正确性和期望符合实际情况。