Path Sum II — Coding Interview Question

In this post, let’s explore the solution for LeetCode “Path Sum II” problem.

Problem Statement

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Solution

This problem is a slight variation of Path Sum.

The problem statements of “Path Sum” and “Path Sum II” are similar in that they both involve finding paths in a binary tree that sum up to a target value. However, there is a key difference between the two:

1. “Path Sum”: The goal is to determine if there exists a path from the root to any leaf node in the binary tree that sums up to the given target value. The task is to return a boolean value indicating whether such a path exists or not.
2. “Path Sum II”: The goal is to find all paths from the root to leaf nodes in the binary tree that sum up to the given target value. Instead of returning just a boolean value, the task is to return a list of all these paths as a result.

So, while “Path Sum” focuses on determining the existence of a single path, “Path Sum II” extends the problem to find…