404.左叶子之和
- 给定二叉树的根节点root，返回所有左叶子之和。
1. 深度优先遍历DFS
- 要点: 在定义递归函数时加入判断是否为左节点的条件, 这样就可以在遍历整棵树时对所有的左节点的值进行相加操作
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def sumOfLeftLeaves(self, root):
"""
:type root: Optional[TreeNode]
:rtype: int
"""
if not root:
return 0
def dfs(node, is_left):
if not node:
return 0
if not node.left and not node.right and is_left:
# 若当前节点是左叶子结点
return node.val
return dfs(node.left, True) + dfs(node.right, False)
return dfs(root, False)
- 时间复杂度: O(n), n为节点个数
- 空间复杂度: O(h), h为树的高度
2. 广度优先遍历BFS
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def sumOfLeftLeaves(self, root):
"""
:type root: Optional[TreeNode]
:rtype: int
"""
if not root:
return 0
total_sum = 0
queue = deque()
# 将根节点入队，并标记它不是左子节点（False）
queue.append((root, False))
while queue:
node, is_left = queue.popleft()
# 如果是左叶子节点，累加其值
if is_left and not node.left and not node.right:
total_sum += node.val
# 将左子节点入队，并标记为左子节点（True）
if node.left:
queue.append((node.left, True))
# 将右子节点入队，并标记为右子节点（False）
if node.right:
queue.append((node.right, False))
return total_sum
-
时间复杂度: 时间复杂度为 O(n)，n 是节点数
-
空间复杂度: 队列中最多存储一层的节点，因此空间复杂度为 O(m)，其中 m 是二叉树的最大宽度（即某一层的最大节点数）
