A simple way to solve this problem

  • 0

    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 {


    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) {
            } // 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.