Path Sum

Question

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.

For 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.

Answer 1

I think the following one looks neet :)

public boolean hasPathSum(TreeNode root, int sum) {
    // Start typing your Java solution below
    // DO NOT write main() function
    if(root==null)
        return false;
    if(root.left==null && root.right==null && root.val==sum)
        return true;
    else
        return hasPathSum(root.left, sum-root.val)||hasPathSum(root.right,sum-root.val);
}

Answer 2

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

        return false;
    }
    bool hasPathSum(TreeNode *root, int sum) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(root == NULL) return false;

        if(root->left == NULL && root->right == NULL && root->val == sum)
            return true;
        if(root->left != NULL && findSub(root->left, sum - root->val)) 
            return true;
        if(root->right != NULL && findSub(root->right, sum - root->val)) 
            return true;

        return false;
    }
};

Answer 3

class Solution {

public:

bool hasPathSum(TreeNode *root, int sum) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function

    if(root==NULL)
        return false;    
    if(root->left==NULL&&root->right==NULL)
        return sum==root->val;                
    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;
}

};

Answer 4

    if( root == NULL)
        return false;
    if( root->left != NULL && root->right == NULL)
        return hasPathSum(root->left, sum - root->val);
    else if( root->left == NULL && root->right != NULL)
        return hasPathSum(root->right, sum - root->val);
    else if( root->left != NULL && root->right != NULL)
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    else
        {
            if(sum == root->val)
                return true;
            else 
                return false;
        }

Answer 5

bool hasPathSum(TreeNode *root, int sum) {
// Start typing your C/C++ solution below
// DO NOT write int main() function

if (root == NULL) return false;
if (root->left == NULL && root->right == NULL)
    return sum == root->val;

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

Answer 6

class Solution { public: int path_sum; bool find_sum;

 bool hasPathSum(TreeNode *root, int sum) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(root==NULL) return 0;
    path_sum=0;
    find_sum=0;
    (void) traverse(root,root,sum);
    return find_sum;

}

void traverse(TreeNode *tt, TreeNode *t1, int sum)
{

    if(tt==NULL) { if(t1->left==NULL && t1->right==NULL && path_sum==sum) find_sum=1; }
    else {
        path_sum+=tt->val;
        (void) traverse(tt->left,tt,sum);
        (void) traverse(tt->right,tt,sum);
        path_sum-=tt->val;
    }

}

};

Answer 7

bool hasPathSum(TreeNode *root, int sum) {
if(root == NULL)
    return false;
if(root->right == NULL && root->left == NULL && root->val == sum)
    return true;
else
    return (hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val));
}

Answer 8

I'm trying to do a non-recursive one.

typedef struct path_element {
struct TreeNode *node;
int level; } path_element;

void addNodeToPath(std::vector<path_element> *path, path_element element)
{
    while (!path->empty()) {
        if (path->back().level >= element.level) {
            path->pop_back();
        } else {
            break;
        }
    }
    path->push_back(element);
}

bool verifyPathSum(std::vector<path_element> *path, int sum) {
    int s = 0;
    std::vector<path_element>::iterator it;

    for (it = path->begin(); it != path->end(); it++) {
        s += it->node->val;
    }

    return (s == sum);
}

bool hasPathSum(TreeNode *root, int sum) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    std::stack<path_element> s;
    std::vector<path_element> v;

    if (!root) {
        return false;
    }

    path_element r;
    r.node = root;
    r.level = 1;
    s.push(r);
    v.push_back(r);

    while (!s.empty()) {
        path_element tmp, p = s.top();
        s.pop();

        addNodeToPath(&v, p);

        if (!(p.node->right) && !(p.node->left)) {
            if (verifyPathSum(&v, sum)) {
                return true;
            }
            continue;
        }

        if ((p.node)->right) {
            tmp.node = (p.node)->right;
            tmp.level = p.level + 1;
            s.push(tmp);
        }
        if ((p.node)->left) {
            tmp.node = (p.node)->left;
            tmp.level = p.level + 1;
            s.push(tmp);
        }
    } // while

    return false;
}

Answer 9

public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
      return helper(root,sum);   
}

public boolean helper(TreeNode root, int sum){

    if(root==null)
        return false;

    int res = sum - root.val;
    if(root.left==null && root.right==null && res==0)
        return true;

   return helper(root.left, res) || helper(root.right, res);
}

}

Answer 10

non-recursive version of preorder travelsal

    if (root == NULL) {
        if (sum == 0) {
            return false;
        } else {
            return false;
        }
    }
    stack<TreeNode*> st;
    st.push(root);
    int stack_value = root->val;
    TreeNode* top;
    TreeNode* child;
    TreeNode* father;
    while(!st.empty()) {
        top = st.top();
        if (top->left!=NULL) {
            st.push(top->left);
            stack_value += top->left->val;
        } else if(top->right != NULL) {
            st.push(top->right);
            stack_value += top->right->val;
        } else {
            //get leaf
            if (stack_value == sum) {
                return true;
            }
            child = top;
            st.pop();
            stack_value -= child->val;
            while(!st.empty()) {
                father = st.top();
                if (father->left == child && father->right == NULL || father->right == child) {
                    child = father;
                    st.pop();
                    stack_value -= child->val;
                } else {
                    st.push(father->right);
                    stack_value += father->right->val;
                    break;
                }
            }
        }
    }
    return false;

Path Sum

Follow this question

Welcome to LeetCode

Related questions