https://leetcode.com/problems/path-sum/description/
Recursion
bool hasPathSum(TreeNode* root, int sum) {
if(!root) return false;
if(!root->left && !root->right && sum==root->val) return true;
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
or,
bool preOrder(TreeNode* node, int sum, int s) {
s += node->val;
if(!node->left && !node->right && s==sum) return true;
return (node->left? preOrder(node->left, sum, s):false) ||
(node->right? preOrder(node->right, sum, s):false);
}
bool hasPathSum(TreeNode* root, int sum) {
if(!root) return false;
return preOrder(root, sum, 0);
}
Iteration
bool hasPathSum(TreeNode* root, int sum) {
if(!root) return false;
stack<TreeNode*> st;
stack<int> sm;
st.push(root);
sm.push(0);
TreeNode* node;
int sn = 0;
while(!st.empty()) {
node = st.top();
st.pop();
sn = sm.top() + node->val;
sm.pop();
if(!node->left && !node->right && sn==sum) return true;
if(node->right) {st.push(node->right); sm.push(sn);}
if(node->left) {st.push(node->left); sm.push(sn);}
}
return false;
}
No comments:
Post a Comment