A simple way to solve this problem


  • 0
    Z

    Using preOrder traversal, record the length of all the path with hash_table when encounter leaf. We only need find whether the sum is in the hash_table after we find every single path.

    class Solution {

    public:

    bool hasPathSum(TreeNode* root, int sum) {
        int path = 0;
        unordered_set<int> result;
        
        PathSum(root, path, result);
        
        if (result.find(sum) == result.end()) {
            return false;
        }
        
        return true;
        
    }
    
    void PathSum(TreeNode* root, int path, unordered_set<int>& result) {
        if (root != NULL) {
            path += root->val;
            PathSum(root->left, path, result);
            PathSum(root->right, path, result);
            if (root->left == NULL && root->right == NULL) {
                result.insert(path);
            } // insert in to hashtable when encountered leaf.
        } 
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.