Path sum iv

Array Hash Table Tree Depth-First Search Binary Tree

62.8% acceptance

Mar 31, 2026

428

522

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

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn path_sum(nums: Vec<i32>) -> i32 {
    use std::collections::HashMap;
    let mut map: HashMap<(i32, i32), i32> = HashMap::new();
    for &num in &nums {
      let d = num / 100;
      let p = (num / 10) % 10;
      let v = num % 10;
      map.insert((d, p), v);
    }
    
    let mut total = 0;
    fn dfs(d: i32, p: i32, cur_sum: i32, map: &HashMap<(i32, i32), i32>, total: &mut i32) {
      if let Some(&v) = map.get(&(d, p)) {
        let cur_sum = cur_sum + v;
        let left = (d + 1, 2 * p - 1);
        let right = (d + 1, 2 * p);
        let has_left = map.contains_key(&left);
        let has_right = map.contains_key(&right);
        if !has_left && !has_right {
          *total += cur_sum;
        } else {
          if has_left { dfs(left.0, left.1, cur_sum, map, total); }
          if has_right { dfs(right.0, right.1, cur_sum, map, total); }
        }
      }
    }
    dfs(1, 1, 0, &map, &mut total);
    total
  }
}