计算给定二叉树的所有左叶子之和。
示例：
3
/
9 20
/
15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-left-leaves
参考：
python
# 404.左子叶之和
class Solution:
def sumOfLeftLeaves(self, root: TreeNode) -> int:
"""
前序递归
:param root:
:return:
"""
if not root:
return 0
# 左子树左叶子和
leftLeftLeavesSum = self.sumOfLeftLeaves(root.left)
# 右子树左叶子和
rightLeftLeavesSum = self.sumOfLeftLeaves(root.right)
curLeftLeafVal = 0
if root.left and not root.left.left and not root.left.right:
curLeftLeafVal = root.left.val # 中
return curLeftLeafVal + leftLeftLeavesSum + rightLeftLeavesSum
class Solution2:
def sumOfLeftLeaves(self, root: TreeNode) -> int:
stack = []
if root:
stack.append(root)
sum = 0
while stack:
# 每次放入当前节点的左节点
curNode = stack.pop()
if curNode.left and not curNode.left.left and not curNode.left.right:
sum += curNode.left.val
if curNode.left:
stack.append(curNode.left)
if curNode.right:
stack.append(curNode.right)
return sum
golang
package binaryTree
import "container/list"
// 递归法
func sumOfLeftLeaves1(root *TreeNode) int {
var res int
findLeft(root, &res)
return res
}
func findLeft(root *TreeNode, res *int) {
if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
*res = *res + root.Left.Val
}
if root.Left != nil {
findLeft(root.Left, res)
}
if root.Right != nil {
findLeft(root.Right, res)
}
}
// 迭代法
func sumOfLeftLeaves2(root *TreeNode) int {
var res int
queue := list.New()
queue.PushBack(root)
for queue.Len() > 0 {
length := queue.Len()
for i:=0;i<length;i++ {
node := queue.Remove(queue.Front()).(*TreeNode)
if node.Left != nil && node.Left.Left == nil && node.Left.Right == nil {
res = res + node.Left.Val
}
if node.Left != nil {
queue.PushBack(node.Left)
}
if node.Right != nil {
queue.PushBack(node.Right)
}
}
}
return res
}