Java solution, Represent tree using HashMap


  • 22

    How do we solve problem like this if we were given a normal tree? Yes, traverse it, keep a root to leaf running sum. If we see a leaf node (node.left == null && node.right == null), we add the running sum to the final result.

    Now each tree node is represented by a number. 1st digits is the level, 2nd is the position in that level (note that it starts from 1 instead of 0). 3rd digit is the value. We need to find a way to traverse this tree and get the sum.

    The idea is, we can form a tree using a HashMap. The key is first two digits which marks the position of a node in the tree. The value is value of that node. Thus, we can easily find a node's left and right children using math.
    Formula: For node xy? its left child is (x+1)(y*2-1)? and right child is (x+1)(y*2)?

    Given above HashMap and formula, we can traverse the tree. Problem is solved!

    class Solution {
        int sum = 0;
        Map<Integer, Integer> tree = new HashMap<>();
        
        public int pathSum(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            
            for (int num : nums) {
                int key = num / 10;
                int value = num % 10;
                tree.put(key, value);
            }
            
            traverse(nums[0] / 10, 0);
            
            return sum;
        }
        
        private void traverse(int root, int preSum) {
            int level = root / 10;
            int pos = root % 10;
            int left = (level + 1) * 10 + pos * 2 - 1;
            int right = (level + 1) * 10 + pos * 2;
            
            int curSum = preSum + tree.get(root);
            
            if (!tree.containsKey(left) && !tree.containsKey(right)) {
                sum += curSum;
                return;
            }
            
            if (tree.containsKey(left)) traverse(left, curSum);
            if (tree.containsKey(right)) traverse(right, curSum);
        }
    }
    

  • 0

    @shawngao: Editorial level explanation, thank you!


  • 0

    Similar idea, but using an integer matrix rather than HashMap:

    class Solution {
        public int pathSum(int[] nums) {
            Integer[][] matrix = new Integer[4 + 1][8 + 1];
            for (int num : nums) {
                int[] node = parseElement(num);
                matrix[node[0]][node[1]] = node[2];
            }
            matrix[0][0] = 0;
            matrix[0][1] = 0;
            helper(matrix, 1, 1);
            return matrix[0][0];
        }
    
        public void helper(Integer[][] matrix, int i, int j) {
            if (matrix[i][j] == null)
                return;
            int base = 2 * (j - 1);
            matrix[0][1] += matrix[i][j];
            if (i == 4 || (matrix[i + 1][base + 1] == null && matrix[i + 1][base + 2] == null)) {
                matrix[0][0] += matrix[0][1];
            } else {
                helper(matrix, i + 1, base + 1);
                helper(matrix, i + 1, base + 2);
            }
            matrix[0][1] -= matrix[i][j];
        }
    
        public int[] parseElement(int num) {
            int[] res = new int[3];
            for (int i = 0; i < 3; i++) {
                res[2 - i] = num % 10;
                num /= 10;
            }
            return res;
        }
    }
    

  • 0
    D

    no need to keep the global sum

    class Solution {
    public:
        int pathSum(vector<int>& nums) {
            if (nums.size() == 0) return 0;
            unordered_map<int, int> tree;
            for (int num : nums) {
                tree[num / 10] = num % 10;
            }
            return pathSum(tree, 0, nums[0] / 10);
        }
        
        int pathSum(unordered_map<int, int> &tree, int prevSum, int curr) {
            if (!tree.count(curr)) return 0;
            int level = curr / 10, pos = curr % 10, val = tree[curr];
            int left = (level + 1) * 10 + 2 * pos - 1;
            int right = (level + 1) * 10 + 2 * pos;
    
            int currSum = prevSum + val;
            if (!tree.count(left) && !tree.count(right)) return currSum;
            return pathSum(tree, currSum, left) + pathSum(tree, currSum, right);
            
        }
    };
    

  • 1
    I

    ONE PASS.

            int[][] map = new int[5][9];
            int ans = 0;
            for (int num : nums) {
                int r = num / 100, c = num % 100 / 10, v = num % 10;
                map[r][c] = v;
                if (r > 1) {
                    int p = map[r - 1][(c + 1) / 2];
                    map[r][c] += Math.abs(p);
                    if (p > 0) {
                        ans -= p;
                        map[r - 1][(c + 1) / 2] = -p;
                    }
                }
                ans += map[r][c];
            }
            return ans;
    

  • 0

    share my solution by traversing the tree "iteratively"

    class Solution {
        public int pathSum(int[] nums) {
            //corner
            if (nums.length == 0) {
                return 0;
            }
    
            //store the node(represent by level and col #) and its corresponding path sum which is the sum of path from root to this node
            Map<Integer, Integer> map = new HashMap<>();
            int sum = 0;
            for (int num : nums) {
                int level = num/100;
                int value = num%10;
                int key = (num - value)/10;
                int col = (num%100 - value)/10;
    
                if (level == 1) {
                    map.put(11, value);
                } else {
                    int upperKey = (level-1) * 10 + (col + 1)/2;
                    map.put(key, value + map.get(upperKey));
                }
            }
    
            //if the node has no children, then add the path sum
            for (int key : map.keySet()) {
                int level = key/10;
                int col = key%10;
    
                int left = 10* (level+1) + col * 2 - 1;
                int right = 10* (level+1) + col * 2 ;
                if (!map.containsKey(left) && !map.containsKey(right)) {
                    sum += map.get(key);
                }
            }
    
            return sum;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.