Leetcode 112 Solution

This article provides solution to leetcode question 112 (path-sum)

https://leetcode.com/problems/path-sum

Solution

/** * Definition for a binary tree node. * 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) { stack<TreeNode*> s;
if (root == NULL) return false;
s.push(root);
int curr = root->val; TreeNode* prev = NULL; while (s.empty() == false) { auto p = s.top();
if (prev == NULL || (prev != p->left && prev != p->right)) { if (p->left) { s.push(p->left); curr += p->left->val; prev = p; } else if (p->right) { s.push(p->right); curr += p->right->val; prev = p; } else { if (curr == sum) return true;
prev = p; curr -= p->val; s.pop(); } } else if (prev == p->left && p->right) { s.push(p->right); curr += p->right->val; prev = p; } else { prev = p; curr -= p->val; s.pop(); } }
return false; } };