Question

666. Path Sum IV

中文文档

Description

If the depth of a tree is smaller than 5, then this tree can be represented by an array of three-digit integers. For each integer in this array:

• The hundreds digit represents the depth d of this node where 1 <= d <= 4.
• The tens digit represents the position p of this node in the level it belongs to where 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 where 0 <= v <= 9.

Given an array of ascending three-digit integers nums representing a binary tree with a depth smaller than 5, return _the sum of all paths from the root towards the leaves_.

It is guaranteed that the given array represents a valid connected binary tree.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= nums.length <= 15
• 110 <= nums[i] <= 489
• nums represents a valid binary tree with depth less than 5.

Solutions

Solution 1

class Solution:
  def pathSum(self, nums: List[int]) -> int:
    def dfs(node, t):
      if node not in mp:
        return
      t += mp[node]
      d, p = divmod(node, 10)
      l = (d + 1) * 10 + (p * 2) - 1
      r = l + 1
      nonlocal ans
      if l not in mp and r not in mp:
        ans += t
        return
      dfs(l, t)
      dfs(r, t)

    ans = 0
    mp = {num // 10: num % 10 for num in nums}
    dfs(11, 0)
    return ans

class Solution {
  private int ans;
  private Map<Integer, Integer> mp;

  public int pathSum(int[] nums) {
    ans = 0;
    mp = new HashMap<>(nums.length);
    for (int num : nums) {
      mp.put(num / 10, num % 10);
    }
    dfs(11, 0);
    return ans;
  }

  private void dfs(int node, int t) {
    if (!mp.containsKey(node)) {
      return;
    }
    t += mp.get(node);
    int d = node / 10, p = node % 10;
    int l = (d + 1) * 10 + (p * 2) - 1;
    int r = l + 1;
    if (!mp.containsKey(l) && !mp.containsKey(r)) {
      ans += t;
      return;
    }
    dfs(l, t);
    dfs(r, t);
  }
}

class Solution {
public:
  int ans;
  unordered_map<int, int> mp;

  int pathSum(vector<int>& nums) {
    ans = 0;
    mp.clear();
    for (int num : nums) mp[num / 10] = num % 10;
    dfs(11, 0);
    return ans;
  }

  void dfs(int node, int t) {
    if (!mp.count(node)) return;
    t += mp[node];
    int d = node / 10, p = node % 10;
    int l = (d + 1) * 10 + (p * 2) - 1;
    int r = l + 1;
    if (!mp.count(l) && !mp.count(r)) {
      ans += t;
      return;
    }
    dfs(l, t);
    dfs(r, t);
  }
};

func pathSum(nums []int) int {
  ans := 0
  mp := make(map[int]int)
  for _, num := range nums {
    mp[num/10] = num % 10
  }
  var dfs func(node, t int)
  dfs = func(node, t int) {
    if v, ok := mp[node]; ok {
      t += v
      d, p := node/10, node%10
      l := (d+1)*10 + (p * 2) - 1
      r := l + 1
      if _, ok1 := mp[l]; !ok1 {
        if _, ok2 := mp[r]; !ok2 {
          ans += t
          return
        }
      }
      dfs(l, t)
      dfs(r, t)
    }
  }
  dfs(11, 0)
  return ans
}