一、问题描述

计算给定二叉树的所有左叶子之和。

二、示例

给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24。

三、方案一：递归法

1、思路

递归遍历整棵树，对于每个节点，检查它的左孩子是否是叶子节点。如果是，则将它的值加到总和中。

2、代码实现

func sumOfLeftLeaves(root *TreeNode) int {
    if root == nil {
        return 0
    }
    sum := 0
    if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
        sum += root.Left.Val
    }
    sum += sumOfLeftLeaves(root.Left)
    sum += sumOfLeftLeaves(root.Right)
    return sum
}

3、复杂度分析

• 时间复杂度：O(n)，其中n是树中节点的数量。我们遍历了树中的每个节点一次。
• 空间复杂度：O(h)，其中h是树的高度。空间复杂度主要取决于递归栈的深度，而递归栈的深度等于树的高度。

四、方案二：迭代法

1、思路

使用迭代方法，通常使用栈或队列来遍历树。对于每个节点，我们检查它的左孩子是否是叶子节点，如果是，则将它的值加到总和中。

2、代码实现

func sumOfLeftLeaves(root *TreeNode) int {
    if root == nil {
        return 0
    }
    sum := 0
    stack := []*TreeNode{root}
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if node.Left != nil && node.Left.Left == nil && node.Left.Right == nil {
            sum += node.Left.Val
        }
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
    }
    return sum
}

3、复杂度分析

• 时间复杂度：O(n)，其中n是树中节点的数量。我们遍历了树中的每个节点一次。
• 空间复杂度：O(n)，其中n是树中节点的数量。空间复杂度主要取决于栈或队列的空间，最坏情况下，树是完全不平衡的，例如每个节点都只有左子节点，这时栈或队列的大小将是O(n)。

五、总结

两种方法都可以有效地解决左叶子之和的问题。递归法更直观，但迭代法在空间复杂度上可能更有优势，特别是在处理大型数据集时。