Java bottom-up recursive O(n) space O(nlogn) time


  • 0

    highest 2 digits uniquely determines the TreeNode position i.e. (level,pos)
    use that as key, lowest 1 digit as value of HashMap tree.
    level = num / 10;
    pos = num % 10;

    To get node's parent, use (level-1, (pos+1)/2)
    To get node's left child, use (level+1, pos2-1), right child (level+1, pos2)

    algorithm

    1. traverse num[] to construct tree map.
    2. traverse num[] again and if a leaf is detected, trace back its root while computing the accumulated sum

    runtime: assuming it is a balanced binary tree of size n
    it has n leaves and therefore n paths made of n*h nodes. h = logn.
    so O(nlogn)

    class Solution {
        public int pathSum(int[] nums) {
            Map<Integer, Integer> tree = new HashMap<>();
            for (int num : nums) {
                tree.put(num / 10, num % 10);
            }
            int sum = 0;
            for (int num : nums) {
                if (isLeaf(num / 10, tree)) {
                    sum += getPathSum(num / 10, tree);
                } 
            }
            return sum;
        }
        
        private boolean isLeaf(int key, Map<Integer, Integer> tree) {
            return !tree.containsKey((key / 10 + 1) * 10 + (key % 10) * 2 - 1) && !tree.containsKey((key / 10 + 1) * 10 + (key % 10) * 2);
        }
        
        private int getPathSum(int key, Map<Integer, Integer> tree) {
            int sum = 0;
            do {
                sum += tree.get(key);
                key = (key / 10 - 1) * 10 + (key % 10 + 1) / 2;
            }
            while (tree.containsKey(key));
            return sum;
        }
    }

Log in to reply
 

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