Path Sum

Path Sum

 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.

---------------------------- codes -----------------------------
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == NULL) {
            return false;
        }
       
        stack<TreeNode*> stack;
        stack.push(root);
        while (stack.size()) {
            TreeNode* cur = stack.top();
            stack.pop();
            if (cur->left == NULL && cur->right == NULL) {
                if (cur->val == sum) {
                    return true;
                }
            } else {//bug here, cannot compare cur->val with sum, because it might be smaller than 0
                if (cur->left) {
                    cur->left->val += cur->val;
                    stack.push(cur->left);
                }
                if (cur->right) {
                    cur->right->val += cur->val;
                    stack.push(cur->right);
                }
            }
        }
        return false;
    }
};