algoadvance

Leetcode 113. Path Sum II

Problem Statement

113. Path Sum II

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.

Clarifying Questions

1. What should be returned if the tree is empty?
   • If the tree is empty, return an empty list.
2. Can we assume that targetSum can be negative?
   • Yes, targetSum can be any integer value including negative numbers.
3. Can node values be negative?
   • Yes, node values can be any integer, including negative numbers.
4. Should the order of paths in the result matter?
   • No, the order of the paths in the result does not matter.

Strategy

1. Tree Traversal:
   • We will use Depth-First Search (DFS) to explore all root-to-leaf paths.
2. Path Tracking:
   • While traversing, keep track of the current path and check the sum of the values.
3. Backtracking:
   • Utilize backtracking to explore all possible paths from root to leaf.
4. Edge Cases:
   • Handle edge cases like an empty tree or a tree with only the root node.

Code

#include <vector>
using namespace std;

// Definition for a binary tree node.
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) {
        vector<vector<int>> result;
        vector<int> currentPath;
        findPaths(root, targetSum, currentPath, result);
        return result;
    }

private:
    void findPaths(TreeNode* node, int targetSum, vector<int>& currentPath, vector<vector<int>>& result) {
        if (!node) return;

        currentPath.push_back(node->val);

        if (!node->left && !node->right && targetSum == node->val) {
            result.push_back(currentPath);
        } else {
            if (node->left) findPaths(node->left, targetSum - node->val, currentPath, result);
            if (node->right) findPaths(node->right, targetSum - node->val, currentPath, result);
        }

        currentPath.pop_back(); // Backtrack
    }
};

Time Complexity

• Time Complexity: (O(N))
  • Each node is visited exactly once until we find all possible paths.
• Space Complexity: (O(H))
  • We use additional space for the recursion call stack, where (H) is the height of the tree.
  • In the worst case, (H = O(N)), where (N) is the number of nodes in the tree.

This solution effectively explores all potential paths in a binary tree to find those paths that equal the given targetSum, using a depth-first search strategy complemented by backtracking.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?