0404-左子叶之和

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

示例:

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
}
上一篇:最小生成树算法(未完成)


下一篇:沟通无限校园网--最小生成树(prim算法)