路径总和 Ⅰ
递归
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(!root) {return false;}
if(!root->left && !root->right && root->val==targetSum) {return true;}
return hasPathSum(root->left, targetSum-root->val) || hasPathSum(root->right, targetSum-root->val);
}
};
迭代
相当于层序遍历，新加一个队列来记录结点的value值，如果某一层某个节点是叶子节点，看当前的sum是不是targetSum，不是就继续
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(!root) {return false;}
queue<TreeNode*> q_for_node;
queue<int> q_for_num;
q_for_node.push(root);
q_for_num.push(root->val);
while(!q_for_node.empty()) {
int size = q_for_node.size();
while(size--) {
TreeNode* tmp = q_for_node.front();
int sum = q_for_num.front();
q_for_node.pop();
q_for_num.pop();
if(!tmp->left && !tmp->right && sum== targetSum) {return true;}
if(tmp->left) {
q_for_node.push(tmp->left);
q_for_num.push(sum + tmp->left->val);
}
if(tmp->right) {
q_for_node.push(tmp->right);
q_for_num.push(sum + tmp->right->val);
}
}
}
return false;
}
};
