Path Sum IV

Similar Problems:

If the depth of a tree is smaller than 5, then this tree can be represented by a list of three-digits integers.

For each integer in this list:

- The hundreds digit represents the depth D of this node, 1 <= D <= 4.
- The tens digit represents the position P of this node in the level it belongs to, 1 <= P <= 8. The position is the same as that in a full binary tree.
- The units digit represents the value V of this node, 0 <= V <= 9.

Given a list of ascending three-digits integers representing a binary with the depth smaller than 5. You need to return the sum of all paths from the root towards the leaves.

Example 1:

Input: [113, 215, 221] Output: 12 Explanation: The tree that the list represents is: 3 / \ 5 1 The path sum is (3 + 5) + (3 + 1) = 12.

Example 2:

Input: [113, 221] Output: 4 Explanation: The tree that the list represents is: 3 \ 1 The path sum is (3 + 1) = 4.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution: bfs

// Blog link: https://code.dennyzhang.com/path-sum-iv // Baisc Ideas: BFS // // map: index -> value // From level i+1 to level i, it's simply (index+1)/2 // // Interesting question: when we do bfs, how we know whether one node is a leaf? // // Complexity: Time O(n), Space O(n) func pathSum(nums []int) int { if len(nums) == 0 { return 0 } res := 0 m := map[int]int{1:nums[0]%10} i, level := 1, 1 index, node := 0, 0 for len(m) != 0{ level++ m2 := map[int]int{} for i<len(nums) && nums[i]<(level+1)*100 { index = (nums[i]%100)/10 node = m[(index+1)/2] m2[index] = node+nums[i]%10 i++ } for key := range m { _, status1 := m2[key*2-1] _, status2 := m2[key*2] // collect leaf nodes at the current layer if status1 == false && status2 == false { res += m[key] } } m = m2 } return res }