JAVA AC Solution (No Recursion Needed, Only Hash used)


  • 0

    Here A HashMap is used to store TreeNodes' positions(depth and level) and values separately. And a Set is used to check if the TreeNode is a leaf. Then traverse the whole array from the end to the start (that is, adding TreeNodes' values from each leaf to the root).

    class Solution {
        public int pathSum(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            int n = nums.length;
            int sum = 0;
            Map<Integer, Integer> map = new HashMap<>();
            Set<Integer> set = new HashSet<>();
            for (int i : nums) {
                map.put(i / 10, i % 10);
            }
            for (int j = n - 1; j >= 0; j--) {
                int key = nums[j] / 10;
                if (set.contains(key)) continue;
                while (key >= 11) {
                    sum += map.get(key);
                    key = (key / 10 - 1) * 10 + (key % 10 + 1) / 2;
                    set.add(key);
                }
            }
            return sum;        
        }
    }

Log in to reply
 

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