/**

 * 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> > ret;

        if(!root)

            return ret;

        stack<TreeNode*> stk;

        vector<int> cur;

        cur.push_back(root->val);

        int curSum = root->val;

        unordered_map<TreeNode*, bool> visited;

        stk.push(root);

        visited[root] = true;

        while(!stk.empty())

        {

            TreeNode* top = stk.top();

            if(!top->left && !top->right)

            {//leaf

                if(curSum == sum)

                    ret.push_back(cur);

            }

            if(top->left && visited[top->left] == false)

            {

                stk.push(top->left);

                visited[top->left] = true;

                cur.push_back(top->left->val);

                curSum += top->left->val;

                continue;

            }

            if(top->right && visited[top->right] == false)

            {

                stk.push(top->right);

                visited[top->right] = true;

                cur.push_back(top->right->val);

                curSum += top->right->val;

                continue;

            }

            stk.pop();

            curSum -= top->val;

            cur.pop_back();

        }

        return ret;

    }

};