Leetcode: Path Sum IV

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:

  1. The hundreds digit represents the depth D of this node, 1 <= D <= 4.
  2. 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.
  3. 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
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.