🥉

Sum of Root To Leaf Binary Numbers

Created

2022/01/11 02:56

문제 번호

1022

카테고리

Tree

Depth-First Search

Binary Tree

Sum of Root To Leaf Binary Numbers - LeetCode

You are given the root of a binary tree where each node has a value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit. For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.

https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/

Code

제출 날짜	시간	메모리
2022/01/11	0 ms	3.2 MB

// 1022. Sum of Root To Leaf Binary Numbers
//
// https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/

// Definition for a binary tree node.
// type TreeNode struct {
//     Val int
//     Left *TreeNode
//     Right *TreeNode
// }

// sumRootToLeaf function accumulates all of the numbers root to leaf as a binary.
// Preorder traverse is required to calculate the root to leaf number.
func sumRootToLeaf(root *TreeNode) int {
	var accumulate func(int, *TreeNode) int
	accumulate = func(bin int, node *TreeNode) int {
		if node == nil {
			return 0
		}
		bin = bin<<1 | node.Val
		if node.Left == nil && node.Right == nil {
			return bin
		}
		return accumulate(bin, node.Left) + accumulate(bin, node.Right)
	}
	return accumulate(0, root)
}
Go
복사