Path Sum II

Path Sum II

 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]
]

----------------------- thinking ---------------------
I'm using unordered_map<TreeNode*, TreeNode*> and stack<pair<TreeNode*, int>> to record the information I need.
In the read codes, a set is used to record the tmp sum in the path, which is greater! save memory as well as run time.

https://oj.leetcode.com/discuss/14724/share-my-non-recursive-solution

---------------------- codes ------------------------------
class Solution {
public:
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<vector<int>> result;
        if (root == NULL) {
            return result;
        }
       
        stack<pair<TreeNode*, int>> stack;
        unordered_map<TreeNode*, TreeNode*> map;
        stack.push(make_pair(root, root->val));
        map[root] = NULL;
        while (stack.size()) {
            pair<TreeNode*, int> cur = stack.top();
            stack.pop();
            if (cur.first->left == NULL && cur.first->right == NULL) {
                if (cur.second == sum) {
                    vector<int> rst;
                    TreeNode *node = cur.first;
                    while (node) {
                        rst.insert(rst.begin(), node->val);
                        node = map[node];
                    }
                    result.push_back(rst);
                }
            } else {
                if (cur.first->left) {
                    stack.push(make_pair(cur.first->left, cur.second + cur.first->left->val));
                    map[cur.first->left] = cur.first;
                }
                if (cur.first->right) {
                    stack.push(make_pair(cur.first->right, cur.second + cur.first->right->val));
                    map[cur.first->right] = cur.first;
                }
            }
        }
        return result;
    }
};

---------------------- read codes ------------------------
vector<vector<int> > pathSum(TreeNode *root, int sum) { vector<vector<int>> result; if(root == NULL) { return result; } stack<TreeNode*> nodeStack; TreeNode *current = root; TreeNode *last = NULL; vector<int> set; int pathSum = 0; while(!nodeStack.empty() || current != NULL) { if(current == NULL) { TreeNode *node = nodeStack.top(); if(node->right != NULL && last != node->right) { current = node->right; } else { last = node; nodeStack.pop(); set.pop_back(); pathSum -= node->val; } } else { nodeStack.push(current); set.push_back(current->val); pathSum += current->val; if(current->left == NULL && current->right == NULL && pathSum == sum) { vector<int> row; for(int i =0;i<set.size();i++) { row.push_back(set[i]); } result.push_back(row); } current = current->left; } } return result; }