LeetCode Path Sum I and II: DFS and Serialization

Overview

DFS (bottom up/top down) could be used to solve the LeetCode Path Sum problem and the path sum I could be solved in non-recursive way by serializing the nodes.

LeetCode Path Sum Problem

(1)

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

(2) The follow ups ask you to print all such paths

Solution and Analysis: DFS and Serialization

(1) DFS (Top Down):

Just use DFS the traverse until we encounter a leaf node, one should keep the sum from the root to the current node on the current path (from top to down), note since it is a tree, there is only one unique path from the root to every node, so when doing the DFS, one can keep the current path as well as the sum over the current path, and when we reach a leaf node, we just add the value of the leaf node and check whether the sum is equal to the given sum or not, if it is equal, we just return true for question (1) and finish, we push the current path into result set and keep DFS for question (2). This approach could solve both path sum I and II consistently, the accepted source code by LeetCode Oj to pass these two Path Sum problem is as follows:

void dfs(int target, TreeNode *root, int prevSum, vector<int> *prevPath, vector< vector<int> > *allPaths) {
    prevPath->push_back(root->val);
    if (NULL == root->left && NULL == root->right) {
        if (prevSum + root->val == target) 
            allPaths->push_back(*prevPath);
    }
    if (root->left) 
        dfs(target, root->left, prevSum + root->val, prevPath, allPaths);
    if (root->right) 
        dfs(target, root->right, prevSum + root->val, prevPath, allPaths);
    prevPath->pop_back(); 
}
vector<vector<int> > pathSum(TreeNode *root, int sum) {
    vector<int> path;
    vector< vector<int> > allPaths;
    if (NULL == root) return allPaths;

    dfs(sum, root, 0, &path, &allPaths);
    return allPaths; 
    // if it is Path Sum I problem, just return !allPath.empty();
}

(2) Two other ways to solve Path Sum I:

There are two more alternatives to tackle Path Sum I: the first is still to use DFS but from a bottom up angle, that is, for the current node we are checking, we only need to see whether there is a path with the sum equal to this a new value (the given sum – node->vale). This idea could be implemented recursively.

The second one is to use either a stack or a queue to serialize all the tree nodes and change the node->val to actually the sum from the root to the node itself, once we have a node with the sum equal to the given sum and it is a leaf node, we stop, otherwise, we keep popping out new nodes from the queue or stack to process its sub-trees again until we find no such a path and thus return false.

Summary

DFS (bottom up/top down) could be used to solve the LeetCode Path Sum problem and the path sum I could be solved in non-recursive way by serializing the nodes.

Written on April 21, 2013