112. Path Sum

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把所有从根到叶子的路径和算出来，存到set里面，然后用sum去set里查。当然如果还想更高效，可以用hash，比如unordered_map。 完整代码如下：

class Solution {
public:
    void dfs(set<int>& vals, int cur, TreeNode* root)
    {
        if (root->left == NULL && root->right == NULL) {
            vals.insert(cur + root->val);
            return;
        }
        if (root->left != NULL) {
            dfs(vals, cur + root->val, root->left);
        }
        if (root->right != NULL) {
            dfs(vals, cur + root->val, root->right);
        }
    }
    bool hasPathSum(TreeNode* root, int sum)
    {
        if (root == NULL)
            return false;
        set<int> vals;
        dfs(vals, 0, root);
        if (vals.count(sum) > 0)
            return true;
        else
            return false;
    }
};

本代码提交AC，用时13MS。
二刷。直接递归判断某一条路径的和是否等于sum就好了，代码如下：

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum)
    {
        if (root == NULL)
            return false;
        if (root->left == NULL && root->right == NULL && root->val == sum)
            return true;
        if (root->left == NULL && root->right == NULL && root->val != sum)
            return false;
        if (root->left != NULL)
            if (hasPathSum(root->left, sum – root->val))
                return true;
        if (root->right != NULL)
            if (hasPathSum(root->right, sum – root->val))
                return true;
        return false;
    }
};

本代码提交AC，用时9MS。