404. 左叶子之和
题目描述
输入一棵二叉树的根节点 root，树用层序数组表示，例如 [3,9,20,null,null,15,7]，null 表示空位置。
如果一个节点没有孩子，并且它是父节点的左孩子，就称它为左叶子。根节点没有父节点，不算左叶子。
返回所有左叶子的值之和。没有左叶子时返回 0。
示例 1
输入：root = [3,9,20,null,null,15,7] 输出：24
解释：左叶子是 9 和 15，和为 24。
示例 2
输入：root = [1] 输出：0
解释：只有根节点，不存在左叶子。
数据范围
- 节点数在
[1, 1000]范围内 -1000 <= Node.val <= 1000
解题思路：深度优先搜索
一个节点自己不知道是左还是右，所以站在父节点上判断：如果左孩子存在且没有孩子，它就是左叶子，直接加上它的值；否则递归去左子树里找。右子树中也可能有左叶子，始终递归。
为什么正确
sumOfLeftLeaves(node) 返回以 node 为根的子树中所有左叶子的和（node 本身不算，因为它的左右归属由父节点决定）。
复杂度分析
时间 O(n)，空间 O(h)，h 为树高。
易错点
根节点单独存在时不是左叶子，[1] 的答案是 0。右孩子即使是叶子也不计入，但右子树内部的左叶子要计入，所以右子树不能跳过。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
res = 0
if root.left and not root.left.left and not root.left.right:
res += root.left.val
else:
res += self.sumOfLeftLeaves(root.left)
return res + self.sumOfLeftLeaves(root.right)class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
int res = 0;
if (root.left != null && root.left.left == null && root.left.right == null) {
res += root.left.val;
} else {
res += sumOfLeftLeaves(root.left);
}
return res + sumOfLeftLeaves(root.right);
}
}class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (!root) {
return 0;
}
int res = 0;
if (root->left && !root->left->left && !root->left->right) {
res += root->left->val;
} else {
res += sumOfLeftLeaves(root->left);
}
return res + sumOfLeftLeaves(root->right);
}
};func sumOfLeftLeaves(root *TreeNode) int {
if root == nil {
return 0
}
res := 0
if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
res += root.Left.Val
} else {
res += sumOfLeftLeaves(root.Left)
}
return res + sumOfLeftLeaves(root.Right)
}var sumOfLeftLeaves = function(root) {
if (!root) {
return 0;
}
let res = 0;
if (root.left && !root.left.left && !root.left.right) {
res += root.left.val;
} else {
res += sumOfLeftLeaves(root.left);
}
return res + sumOfLeftLeaves(root.right);
};function sumOfLeftLeaves(root: TreeNode | null): number {
if (!root) {
return 0;
}
let res = 0;
if (root.left && !root.left.left && !root.left.right) {
res += root.left.val;
} else {
res += sumOfLeftLeaves(root.left);
}
return res + sumOfLeftLeaves(root.right);
}其他解法
两种方法都访问每个节点一次；深度优先搜索代码短，广度优先搜索用队列避免了递归深度问题。
解法 2：广度优先搜索 时间 O(n)，空间 O(n)
用队列按层遍历二叉树。取出一个节点后检查它的左孩子：左孩子是叶子就把值加入答案，否则把左孩子入队。右孩子不是叶子时入队，右叶子直接忽略。
不使用递归，树退化成链时也不会栈溢出。需要显式维护队列，代码比递归长。
from collections import deque
class Solution:
def sumOfLeftLeaves(self, root):
if not root:
return 0
res = 0
q = deque([root])
while q:
node = q.popleft()
if node.left:
if not node.left.left and not node.left.right:
res += node.left.val
else:
q.append(node.left)
if node.right:
if node.right.left or node.right.right:
q.append(node.right)
return resclass Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
int res = 0;
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (node.left != null) {
if (node.left.left == null && node.left.right == null) res += node.left.val;
else q.offer(node.left);
}
if (node.right != null && (node.right.left != null || node.right.right != null)) q.offer(node.right);
}
return res;
}
}class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (!root) return 0;
int res = 0;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node->left) {
if (!node->left->left && !node->left->right) res += node->left->val;
else q.push(node->left);
}
if (node->right && (node->right->left || node->right->right)) q.push(node->right);
}
return res;
}
};func sumOfLeftLeaves(root *TreeNode) int {
if root == nil {
return 0
}
res := 0
q := []*TreeNode{root}
for len(q) > 0 {
node := q[0]
q = q[1:]
if node.Left != nil {
if node.Left.Left == nil && node.Left.Right == nil {
res += node.Left.Val
} else {
q = append(q, node.Left)
}
}
if node.Right != nil && (node.Right.Left != nil || node.Right.Right != nil) {
q = append(q, node.Right)
}
}
return res
}var sumOfLeftLeaves = function(root) {
if (!root) return 0;
let res = 0;
const q = [root];
let head = 0;
while (head < q.length) {
const node = q[head++];
if (node.left) {
if (!node.left.left && !node.left.right) res += node.left.val;
else q.push(node.left);
}
if (node.right && (node.right.left || node.right.right)) q.push(node.right);
}
return res;
};function sumOfLeftLeaves(root: TreeNode | null): number {
if (!root) return 0;
let res = 0;
const q: TreeNode[] = [root];
let head = 0;
while (head < q.length) {
const node = q[head++];
if (node.left) {
if (!node.left.left && !node.left.right) res += node.left.val;
else q.push(node.left);
}
if (node.right && (node.right.left || node.right.right)) q.push(node.right);
}
return res;
}