Easy to Understand Iterative Solution


  • 0
    class Solution {
        public int pathSum(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            int max = 0;
            for (int num : nums) {
                max = Math.max(max, num / 100);
            }
            int[] tree = new int[1 << max];
            Arrays.fill(tree, -1);
            for (int num : nums) {
                int index = (1 << ((num / 100) - 1)) + ((num / 10) % 10 - 1);
                tree[index] = num % 10;
            }
            int res = 0;
            int n = tree.length;
            for (int i = n - 1; i >= 1; i--) {
                if (tree[i] == -1 || (i * 2 < n && tree[i * 2] != -1)|| (i * 2 + 1 < n && tree[i * 2 + 1] != -1)) continue;
                int j = i;
                while (j > 0) {
                    res += tree[j];
                    j /= 2;
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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