Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/666.html
666. Path Sum IV (Medium)
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
Dof this node,1 <= D <= 4. - The tens digit represents the position
Pof 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
Vof 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.
Companies:
Alibaba
Related Topics:
Tree
Similar Questions:
Solution 1.
-
class Solution { public int pathSum(int[] nums) { if (nums == null || nums.length == 0) return 0; Map<Integer, Integer> depthPositionValueMap = new HashMap<Integer, Integer>(); for (int num : nums) { int depthPosition = num / 10, value = num % 10; depthPositionValueMap.put(depthPosition, value); } Queue<int[]> queue = new LinkedList<int[]>(); int num0 = nums[0]; queue.offer(new int[]{num0 / 10, num0 % 10}); int sum = 0; while (!queue.isEmpty()) { int[] depthPositionValue = queue.poll(); int depthPosition = depthPositionValue[0], value = depthPositionValue[1]; int depth = depthPosition / 10, position = depthPosition % 10; int leftDepthPosition = (depth + 1) * 10 + position * 2 - 1, rightDepthPosition = (depth + 1) * 10 + position * 2; int left = depthPositionValueMap.getOrDefault(leftDepthPosition, -1), right = depthPositionValueMap.getOrDefault(rightDepthPosition, -1); if (left < 0 && right < 0) sum += value; else { if (left >= 0) { int leftValue = left % 10; queue.offer(new int[]{leftDepthPosition, value + leftValue}); } if (right >= 0) { int rightValue = right % 10; queue.offer(new int[]{rightDepthPosition, value + rightValue}); } } } return sum; } } ############ 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); } } -
// OJ: https://leetcode.com/problems/path-sum-iv/ // Time: O(N) // Space: O(N) class Solution { public: int pathSum(vector<int>& nums) { unordered_map<int, int> m; for (int n : nums) { m[n / 10] = n % 10; } int sum = 0; for (int n : nums) { int d = n / 100, p = n / 10 % 10, v = m[d * 10 + p]; int left = (d + 1) * 10 + p * 2 - 1, right = left + 1; if (m.count(left)) m[left] += v; if (m.count(right)) m[right] += v; if (m.count(left) == 0 && m.count(right) == 0) sum += v; } return sum; } }; -
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 -
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 }