Massive Algorithms: LeetCode

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.

X. Recursive https://discuss.leetcode.com/topic/39179/easy-5-lines-and-clean-java-solution

public boolean hasPathSum(TreeNode root, int sum) {    
  if (root == null)
     return false;
        
  if (root.left == null && root.right == null && root.val == sum) // Leaf check
     return true;
        
  return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

https://discuss.leetcode.com/topic/15573/a-java-concise-solution

public boolean hasPathSum(TreeNode root, int sum) {
   if(root == null){
     return false;
   }
   if(root.left == null && root.right == null){
      return (root.val == sum);
   }
   return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
       
}

Also check http://www.geeksforgeeks.org/root-to-leaf-path-sum-equal-to-a-given-number/

public boolean hasPathSum(TreeNode root, int sum) {

        if (root == null)   // Empty tree

            return false;

        // It is a leaf and its value is the path sum

        if (root.val == sum && root.left == null && root.right == null)

            return true;

        // A tree has the path sum if either its left subtree or right subtree

        // has the path sum of (sum-root.val)

        if (hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val))

            return true;

        return false;

}

Also check http://codercareer.blogspot.com/2011/09/no-04-paths-with-specified-sum-in.html
http://www.programcreek.com/2013/01/leetcode-path-sum/
It's better to create a pair with Node + accSu, and store the pair in one Queue, it's easier to code.

    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
 
        LinkedList<TreeNode> nodes = new LinkedList<TreeNode>();
        LinkedList<Integer> values = new LinkedList<Integer>();
 
        nodes.add(root);
        values.add(root.val);
 
        while(!nodes.isEmpty()){
            TreeNode curr = nodes.poll();
            int sumValue = values.poll();
 
            if(curr.left == null && curr.right == null && sumValue==sum){
                return true;
            }
 
            if(curr.left != null){
                nodes.add(curr.left);
                values.add(sumValue+curr.left.val);
            }
 
            if(curr.right != null){
                nodes.add(curr.right);
                values.add(sumValue+curr.right.val);
            }
        }
 
        return false;
    }

BFS

http://www.programcreek.com/2013/01/leetcode-path-sum/

    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
 
        LinkedList<TreeNode> nodes = new LinkedList<TreeNode>();
        LinkedList<Integer> values = new LinkedList<Integer>();
 
        nodes.add(root);
        values.add(root.val);
 
        while(!nodes.isEmpty()){
            TreeNode curr = nodes.poll();
            int sumValue = values.poll();
 
            if(curr.left == null && curr.right == null && sumValue==sum){
                return true;
            }
 
            if(curr.left != null){
                nodes.add(curr.left);
                values.add(sumValue+curr.left.val);
            }
 
            if(curr.right != null){
                nodes.add(curr.right);
                values.add(sumValue+curr.right.val);
            }
        }
 
        return false;
    }
}

http://gongxuns.blogspot.com/2012/12/leetcodepath-sum.html

    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null) return false;
        
        LinkedList<TreeNode> nodes = new LinkedList<TreeNode>();
        LinkedList<Integer> accSums = new LinkedList<Integer>();
        nodes.add(root);
        accSums.add(root.val);
        
        while(!nodes.isEmpty()){
            TreeNode node = nodes.poll();
            Integer accSum = accSums.poll();
            if(node.left==null && node.right==null && accSum==sum)
                return true;
            if(node.left!=null){
                nodes.add(node.left);
                accSums.add(accSum+node.left.val);
            }
            if(node.right!=null){
                nodes.add(node.right);
                accSums.add(accSum+node.right.val);
            }
        }
        return false;
    }

    public boolean hasPathSum(TreeNode root, int sum) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(root==null) return false;
        
        LinkedList<TreeNode> nodes = new LinkedList<TreeNode>();
        LinkedList<Integer> accSums = new LinkedList<Integer>();
        nodes.add(root);
        accSums.add(root.val);
        
        while(!nodes.isEmpty()){
            TreeNode node = nodes.poll();
            Integer accSum = accSums.poll();
            if(node.left==null && node.right==null && accSum==sum)
                return true;
            if(node.left!=null){
                nodes.add(node.left);
                accSums.add(accSum+node.left.val);
            }
            if(node.right!=null){
                nodes.add(node.right);
                accSums.add(accSum+node.right.val);
            }
        }
        return false;
    }

X. PreOrder Non-recursive Version
https://leetcode.com/discuss/22112/my-java-no-recursive-method
https://leetcode.com/discuss/46883/java-solution-both-recursion-and-iteration
public boolean hasPathSum(TreeNode root, int sum) { Stack<TreeNode> stack = new Stack<TreeNode>(); Stack<Integer> sums = new Stack<Integer>(); stack.push(root); sums.push(sum); while(!stack.isEmpty()&&(root!=null)){ int value = sums.pop(); TreeNode top = stack.pop(); if(top.left==null&&top.right==null&&top.val==value){ return true; } if(top.right!=null){ stack.push(top.right); sums.push(value-top.val); } if(top.left!=null){ stack.push(top.left); sums.push(value-top.val); } } return false; }

X. Post-Order
https://leetcode.com/discuss/8215/accepted-by-using-postorder-traversal
bool hasPathSum(TreeNode *root, int sum) { stack<TreeNode *> s; TreeNode *pre = NULL, *cur = root; int SUM = 0; while (cur || !s.empty()) { while (cur) { s.push(cur); SUM += cur->val; cur = cur->left; } cur = s.top(); if (cur->left == NULL && cur->right == NULL && SUM == sum) { return true; } if (cur->right && pre != cur->right) { cur = cur->right; } else { pre = cur; s.pop(); SUM -= cur->val; cur = NULL; } } return false; }
Read full article from LeetCode - Path Sum | Darren's Blog

LeetCode - Path Sum

Labels

Popular Posts