Short Java 8 and dfs solution


  • 2

    The idea is to first represent the tree as a map, that contains the tree in the form of
    Node position number --> Node value , where the Node number is the position of the node in a complete tree.

    Then, we just do a dfs on the above tree to accumulate all the root to leaf path sums.

    Lets take a tree example
                                              10
                                             /  \
                                           20     30
                                          / \     / \
                                        40  50  60   70
    

    For the above tree,
    the node positions are as follows,
    root's position = 1,
    left child position = parent_position * 2
    right child position = parent_position * 2 + 1
    Based on the above complete tree positions, the map generated for the above example would be
    1 --> 10
    2 --> 20
    3 --> 30
    4 --> 40
    5 --> 50
    6 --> 60
    7 --> 70

    To generate these positions from the given input,
    if the input number is 314
    we extract the digits to level = 3, positionInLevel = 1, value = 4
    and the formula I arrived at to get the node's position in complete tree = [2 ^ (level-1)] + positionInLevel - 1

    Now that we have the above map generated,
    we do a simple dfs starting from the root, and keep accumulating the sum, once we reach a leaf, we add the accumulated sum to the result.

        public int pathSum(int[] nums) {
            Map<Integer, Integer> positionToNodeMap = new HashMap<>();
            Arrays.stream(nums).forEach( num -> {
                int[] digits = IntStream.range(0, 3).map(i -> (num + "").charAt(i) - '0').toArray();
                positionToNodeMap.put((int)Math.pow(2, digits[0] - 1) - 1 + digits[1], digits[2]);
            });
            int[] res = new int[1];
            dfs(1, 0, res, positionToNodeMap);
            return res[0];
        }
    
       private void dfs(int cur, int sum, int[] res, Map<Integer, Integer> map) {
            if(!map.containsKey(cur)) return;
            int left = cur * 2, right = cur * 2 + 1, totalSum = sum + map.get(cur);
            if(!map.containsKey(left) && !map.containsKey(right)) { res[0] += totalSum; return; } // Leaf node
            dfs(left, totalSum, res, map);
            dfs(right, totalSum, res, map);
        }
    

Log in to reply
 

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