1358. Path Sum

DFS recursion:
class Solution { public: /** * @param root: the tree * @param sum: the sum * @return: if the tree has a root-to-leaf path */ bool pathSum(TreeNode * root, int sum) { // Write your code here. if(root == NULL){ return sum == 0; } bool left = pathSum(root->left, sum - root->val); bool right = pathSum(root->right, sum - root->val); return left || right; } };

BFS iteration:
class Solution { public: /** * @param root: the tree * @param sum: the sum * @return: if the tree has a root-to-leaf path */ struct node{ TreeNode* tN; int sum; node(TreeNode* tN, int sum){ this->tN = tN; this->sum = sum; } }; bool pathSum(TreeNode * root, int sum) { // Write your code here. if(root == NULL){ return sum == 0; } std::queue<node*> q; q.push(new node(root, root->val)); while(!q.empty()){ node* tmp = q.front(); q.pop(); TreeNode *cur = tmp->tN; int curSum = tmp->sum; if(cur->left == NULL && cur->right == NULL && curSum == sum){ return true; } if(cur->left){ q.push(new node(cur->left, curSum + cur->left->val)); } if(cur->right){ q.push(new node(cur->right, curSum + cur->right->val)); } } return false; } };