路径总和 Ⅰ

递归

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;

    }
};