LeetCode 404. 左叶子之和

Categories:

题目描述
思路分析
参考代码

题目描述

🔥 404. 左叶子之和

思路分析

我们可以使用迭代的方法来遍历二叉树，利用队列来实现广度优先搜索。在遍历过程中，我们需要判断当前节点是否是左叶子节点。如果是，则将其值加到总和中。具体步骤如下：

初始化一个队列，将根节点入队。

进行循环，直到队列为空：

取出队列的第一个节点。

检查该节点的左子节点：

如果左子节点存在且没有子节点，则将其值加到总和中。

将当前节点的左右子节点（如果存在）入队。

返回总和。

参考代码

func sumOfLeftLeaves(root *TreeNode) int {
	var sum int

	var dfs func(node *TreeNode, isLeft bool)
	dfs = func(node *TreeNode, isLeft bool) {
		if node == nil {
			return
		}

		// 判断当前节点是否是左叶子节点
		if isLeft && node.Left == nil && node.Right == nil {
			sum += node.Val
		}

		// 递归遍历左子树和右子树
		dfs(node.Left, true)   // 左子树是左叶子
		dfs(node.Right, false) // 右子树不是左叶子
	}

	dfs(root, false) // 从根节点开始，根节点不是左叶子
	return sum
}

时间复杂度：O (N)，其中 N 是二叉树的节点数。我们需要遍历每个节点一次。

空间复杂度：O (H)，其中 H 是树的高度。递归调用栈的最大深度为树的高度。

func sumOfLeftLeaves(root *TreeNode) int {
	if root == nil {
		return 0
	}

	sum := 0
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// 弹出队首节点
		node := queue[0]
		queue = queue[1:]

		// 判断左子节点是否是左叶子
		if node.Left != nil {
			if node.Left.Left == nil && node.Left.Right == nil {
				sum += node.Left.Val
			} else {
				queue = append(queue, node.Left) // 左子节点入队
			}
		}

		// 右子节点入队
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}

	return sum
}

时间复杂度：O(N)，其中 N 是二叉树的节点数。每个节点遍历一次。

空间复杂度：O(W)，其中 W 是树的最大宽度，队列的最大长度。

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/28113436