666. Path Sum IV

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public: int pathSum(vector& nums) { int ans = 0; vector> tree(4, vector(8, -1)); for (const int num : nums) { const int d = num / 100 - 1; const int p = (num % 100) / 10 - 1; const int v = num % 10; tree[d][p] = v; } dfs(tree, 0, 0, 0, ans); return ans; } private: void dfs(const vector>& tree, int i, int j, int path, int& ans) { if (tree[i][j] == -1) return; if (i == 3 || max(tree[i + 1][j * 2], tree[i + 1][j * 2 + 1]) == -1) { ans += path + tree[i][j]; return; } dfs(tree, i + 1, j * 2, path + tree[i][j], ans); dfs(tree, i + 1, j * 2 + 1, path + tree[i][j], ans); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public int pathSum(int[] nums) { int[][] tree = new int[4][8]; Arrays.stream(tree).forEach(A -> Arrays.fill(A, -1)); for (final int num : nums) { final int d = num / 100 - 1; final int p = (num % 100) / 10 - 1; final int v = num % 10; tree[d][p] = v; } dfs(tree, 0, 0, 0); return ans; } private int ans = 0; private void dfs(int[][] tree, int i, int j, int path) { if (tree[i][j] == -1) return; if (i == 3 || Math.max(tree[i + 1][j * 2], tree[i + 1][j * 2 + 1]) == -1) { ans += path + tree[i][j]; return; } dfs(tree, i + 1, j * 2, path + tree[i][j]); dfs(tree, i + 1, j * 2 + 1, path + tree[i][j]); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution: def pathSum(self, nums: List[int]) -> int: ans = 0 tree = [[-1] * 8 for _ in range(4)] for num in nums: d = num // 100 - 1 p = (num % 100) // 10 - 1 v = num % 10 tree[d][p] = v def dfs(i: int, j: int, path: int) -> None: nonlocal ans if tree[i][j] == -1: return if i == 3 or max(tree[i + 1][j * 2], tree[i + 1][j * 2 + 1]) == -1: ans += path + tree[i][j] return dfs(i + 1, j * 2, path + tree[i][j]) dfs(i + 1, j * 2 + 1, path + tree[i][j]) dfs(0, 0, 0) return ans