#666 - Path Sum IV - LeetCode JavaScript Solutions

#666 - Path Sum IV

Problem Description

If the depth of a tree is smaller than 5, then this tree can be represented by an array of three-digit integers. You are given an ascending array nums consisting of three-digit integers representing a binary tree with a depth smaller than 5, where for each integer:

The hundreds digit represents the depth d of this node, where 1 <= d <= 4.
The tens digit represents the position p of this node within its level, where 1 <= p <= 8, corresponding to its position in a full binary tree.
The units digit represents the value v of this node, where 0 <= v <= 9.

Return the sum of all paths from the root towards the leaves.

It is guaranteed that the given array represents a valid connected binary tree.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var pathSum = function(nums) {
  const nodeMap = new Map();

  for (const num of nums) {
    const depth = Math.floor(num / 100);
    const position = Math.floor((num % 100) / 10);
    const value = num % 10;
    nodeMap.set(`${depth}-${position}`, value);
  }

  return dfs(1, 1, 0);

  function dfs(depth, position, currentSum) {
    const key = `${depth}-${position}`;
    if (!nodeMap.has(key)) return 0;

    const nodeValue = nodeMap.get(key);
    const pathSum = currentSum + nodeValue;

    const leftChild = `${depth + 1}-${position * 2 - 1}`;
    const rightChild = `${depth + 1}-${position * 2}`;

    if (!nodeMap.has(leftChild) && !nodeMap.has(rightChild)) {
      return pathSum;
    }

    return dfs(depth + 1, position * 2 - 1, pathSum)
      + dfs(depth + 1, position * 2, pathSum);
  }
};