One recursion and a vector to save the value C++ code


  • 0
    bool hasPathSum(TreeNode *root, int sum) {
        if(root==NULL)
            return false;
        vector<int> vec;
        return inOrderTrav(root,vec,sum);
    }
    
    bool inOrderTrav(TreeNode *root,vector<int> &vec,const int &sum)
    {
        if(root!=NULL)
        {
            vec.push_back(root->val);
            if(root->left!=NULL)
                if(inOrderTrav(root->left,vec,sum))
                    return true;
            if(root->right!=NULL)
                if(inOrderTrav(root->right,vec,sum))
                    return true;
            if(root->left==NULL&&root->right==NULL&&cal(vec)==sum)
                return true;
            vec.pop_back();
        }
        return false;
    }
    
    int cal(vector<int> &vec)
    {
        vector<int>::iterator ive = vec.begin();
        int root_to_leaf = 0;
        for(;ive!=vec.end();ive++)
        {
            root_to_leaf += *ive;
        }
        return root_to_leaf;
    }

Log in to reply
 

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