_666. Path Sum IV.md

666. Path Sum IV

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 03, 2024

Last updated : July 03, 2024

---

Related Topics : Array, Hash Table, Tree, Depth-First Search, Binary Tree

Acceptance Rate : 62.5 %

---

              1, 1
             /    \__
        __2, 1       2, 2
       /     \      /    \
    3, 1    3, 2  3, 3    3, 4

1,1
2,1 2,2
3,1 3,2 3,3 3,4

---

Solutions

• m666.py

Python

m666.py

class Solution:
    def pathSum(self, nums: List[int]) -> int:
        vals = {}
        leaves = set()
        for num in nums :
            depth = num // 100
            pos = (num // 10) % 10
            val = num % 10

            indx = (depth, pos)
            parentIndx = (depth - 1, (pos + 1) // 2)
            leaves.add(indx)
            
            if parentIndx in leaves :
                leaves.remove(parentIndx)
                vals[indx] = vals[parentIndx] + val
            elif parentIndx in vals :
                vals[indx] = vals[parentIndx] + val
            else :
                vals[indx] = val

        output = 0
        for leaf in leaves :
            output += vals[leaf]

        return output