LeetCode 112. Path Sum [Easy] [C++] 解題筆記

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

想法:

        這題也是直接 DFS 或 BFS 即可，tree 相關的題目 BFS與 DFS 真的很重要阿！

完整程式碼:

解法一(recursive):

class Solution {

public:

    bool hasPathSum(TreeNode* root, int sum) {

        if (root == NULL) { return false; }

        if (root->left == NULL && root->right == NULL && sum - root->val == 0) { return true; }

        return hasPathSum(root->left,sum-root->val) || hasPathSum(root->right,sum-root->val);

    }

};

解法二(iterative):

class Solution {

public:

    bool hasPathSum(TreeNode* root, int sum) {

        if (root == NULL) { return false; }

        bool check = false;

        queue<pair<TreeNode*,int>> q;

        q.push(make_pair(root,0));

        while(!q.empty()) {

            auto q_size = q.size();

            for (size_t i = 0; i < q_size; i++) {

                auto cur_pair = q.front();

                q.pop();

                auto cur = cur_pair.first;

                auto tmp_sum = cur_pair.second+cur->val;

                // reach leaf

                if (cur->left == NULL && cur->right == NULL) {

                    if (tmp_sum == sum) {

                        check = true;

                        break;

                    }

                }

                if (cur->left != NULL)                                      

   q.push(make_pair(cur->left,tmp_sum));

                if (cur->right != NULL)

                   q.push(make_pair(cur->right,tmp_sum));

            }

            if (check) { break; }

        }

        return check;

    }

};