2022/06/25

Leetcode Note: Go - Sum of Leaves

Add Binary - LeetCode
https://leetcode.com/problems/add-binary/

  • Go 言語で取り組んだメモ

所感

  • binary tree が渡されるので末端 leaf node の合計値を int で return する

回答

Go BFS solution - LeetCode Discuss
https://leetcode.com/problems/sum-of-left-leaves/discuss/1109765/Go-BFS-solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumOfLeftLeaves(root *TreeNode) int {
	if root == nil {
		return 0
	}

	var q []*TreeNode
	q = append(q, root)
	sum := 0

	for len(q) > 0 {
		size := len(q)
		for i := 0; i < size; i++ {
			node := q[0]
			q = q[1:]

			if node.Left != nil && isLeaf(node.Left) {
				sum += node.Left.Val
			}

			if node.Left != nil {
				q = append(q, node.Left)
			}

			if node.Right != nil {
				q = append(q, node.Right)
			}
		}
	}

	return sum
}

func isLeaf(root *TreeNode) bool {
	return root.Right == nil && root.Left == nil
}
  • 再帰と見せかけて再帰ではない
  • for ループで Leaf Node か判別しつつ sum への加算を行っていく

See Also