</>Ali · LeetCode
#0113·MediumTrees

Path Sum II

LeetCode #113 · Medium · Trees · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Iterative DFS using Stack

Use a stack to store pairs of (node, path). For each node, track the path from root to that node. When we reach a leaf node, check if the path sum equals targetSum. If so, add the path to the result.

Time
O(n * h)
visit each node and for each leaf, sum the path
Space
O(h^2)
stack stores paths of length up to h
Problem description(from LeetCode)

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.

Examples

Example 1
Input:
root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output:
[[5,4,11,2],[5,8,4,5]]
Note:
There are two paths whose sum equals targetSum: 5 + 4 + 11 + 2 = 22 5 + 8 + 4 + 5 = 22
Example 2
Input:
root = [1,2,3], targetSum = 5
Output:
[]
Example 3
Input:
root = [1,2], targetSum = 0
Output:
[]

Constraints

  • •The number of nodes in the tree is in the range [0, 5000].
  • •-1000 <= Node.val <= 1000
  • •-1000 <= targetSum <= 1000

C++ Solution

solution.cpp
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

class Solution {
public:
vector<vector<int>> pathSum(TreeNode *root, int targetSum) {
    if (root == nullptr) return {};

    vector<vector<int>> res;
    stack<pair<TreeNode *, vector<int>>> s;
    s.push({root, {root->val}});

    while (!s.empty()) {
      pair<TreeNode *, vector<int>> top = s.top();
      s.pop();
      TreeNode *node = top.first;
      vector<int> currentPath = top.second;
      int currentSum = sumVector(currentPath);

      if (node->left == nullptr && node->right == nullptr &&
          currentSum == targetSum) {
        res.push_back(currentPath);
      }

      if (node->right != nullptr) {
        currentPath.push_back(node->right->val);
        s.push({node->right, currentPath});
        currentPath.pop_back();
      }

      if (node->left != nullptr) {
        currentPath.push_back(node->left->val);
        s.push({node->left, currentPath});
        currentPath.pop_back();
      }
    }

    return res;
  }

private:
  int sumVector(vector<int> v) {
    int sum = 0;
    for (auto c : v) {
      sum += c;
    }
    return sum;
  }
};

More Trees problems