Tap here to switch tabs
Problem
Submissions

Problem: Path Sum IV

Try to solve the Path Sum IV problem.

Statement

Given a sorted integer array nums representing a binary tree with depth less than 55, return the sum of all root to leaf path values.

The tree is represented by an array of three digit integers where each integer encodes a node:

  • The hundreds digit represents the depth dd of the node, where 1≤d≤41 \le d \le 4.

  • The tens digit represents the position pp of the node at that depth, where 1≤p≤81 \le p \le 8.

  • The units digit represents the value vv of the node, where 0≤v≤90 \le v \le 9.

For a node at depth dd and position pp:

  • Its left child is located at depth d+1d + 1 and position 2⋅p−12 \cdot p - 1.

  • Its right child is located at depth d+1d + 1 and position 2⋅p2 \cdot p.

A leaf is a node with no children. A root to leaf path sum is the sum of all node values along a path from the root node to a leaf node.

Constraints:

  • 1≤1 \le nums.length ≤15\le 15

  • 110≤110 \le nums[i] ≤489\le 489

  • nums represents a valid binary tree with depth less than 55.

  • nums is sorted in ascending order.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Path Sum IV

Try to solve the Path Sum IV problem.

Statement

Given a sorted integer array nums representing a binary tree with depth less than 55, return the sum of all root to leaf path values.

The tree is represented by an array of three digit integers where each integer encodes a node:

  • The hundreds digit represents the depth dd of the node, where 1≤d≤41 \le d \le 4.

  • The tens digit represents the position pp of the node at that depth, where 1≤p≤81 \le p \le 8.

  • The units digit represents the value vv of the node, where 0≤v≤90 \le v \le 9.

For a node at depth dd and position pp:

  • Its left child is located at depth d+1d + 1 and position 2⋅p−12 \cdot p - 1.

  • Its right child is located at depth d+1d + 1 and position 2⋅p2 \cdot p.

A leaf is a node with no children. A root to leaf path sum is the sum of all node values along a path from the root node to a leaf node.

Constraints:

  • 1≤1 \le nums.length ≤15\le 15

  • 110≤110 \le nums[i] ≤489\le 489

  • nums represents a valid binary tree with depth less than 55.

  • nums is sorted in ascending order.