[LeetCode] Path Sum I && II

Path Sum I

Problem Statement (link):

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.

Analysis:
This problem is a variation of tree traversal. We DFS the binary tree to find if any root-to-leaf path has the same value sum. We continue searching until we find a path.

Code:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root==NULL) return false;
        return trav(root, 0, sum);
    }

    bool trav(TreeNode *node, int pathSum, int sum) {
        bool result = false;
        pathSum += node->val;
        if (node->left==NULL && node->right==NULL)
            if (pathSum==sum)
                return true;
        if (node->left!=NULL)
            result = trav(node->left, pathSum, sum);
        if (!result && node->right!=NULL)
            result = trav(node->right, pathSum, sum);
        return result;
    }
};

Path Sum II

Problem Statement (link):

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,

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

return

[
   [5,4,11,2],
   [5,8,4,5]
]

Analysis:
The idea is basically the same as the previous problem. But instead of updating the value sum, we store the nodes as we traverse down the tree. When we reach the leaf, we check if the sum value of all nodes in the path equals the expected sum, if so, we push the path to out vector.

It is important to pop_back the node after we push_back it into path vector. This ensures that the path vector only stores the nodes in the current path, and thus we could reuse the path vector as we traverse. This is a common trick in tree traversal.

Code:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<vector<int> > out;
        if (root==NULL) return out;
        vector<int> path;
        path.push_back(root->val);
        recur(root, sum, out, path);
        return out;
    }
    void recur(TreeNode *node, int sum, vector<vector<int>> &out, vector<int> &path) {
        if (node->left==NULL && node->right==NULL) {
            int temp=0;
            for (int i=0; i<path.size(); i++) temp+=path[i];
            if (temp==sum) out.push_back(path);
            return;
        }

        if (node->left!=NULL) {
            path.push_back(node->left->val);
            recur(node->left, sum, out, path);
            path.pop_back();
        }
        if (node->right!=NULL) {
            path.push_back(node->right->val);
            recur(node->right, sum, out, path);
            path.pop_back();
        }
    }
};