My Java solutions using Recursion and Iteration (Queue and Stack)


  • 1
    C

    recursion:

        public class Solution {
        //recursion
        public boolean hasPathSum(TreeNode root, int sum) {
            if (root==null) return false;
            //if (sum<root.val) 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));
        }
    }
    

    Queue:

    public class Solution {
    //Queue
    public boolean hasPathSum(TreeNode root, int sum) {
        Queue<TreeNode> qNode=new LinkedList<TreeNode>();
        Queue<Integer> qSum=new LinkedList<Integer>();
        
        if(root==null) return false;
        
        qNode.add(root);
        qSum.add(sum);
        
        while (!qNode.isEmpty()) {
            TreeNode curNode=qNode.remove();
            int curSum=qSum.remove();
            
            if (curNode.left==null && curNode.right==null && curSum==curNode.val) return true;
            if (curNode.left!=null) {
                qNode.add(curNode.left);
                qSum.add(curSum-curNode.val);
            }
            if (curNode.right!=null) {
                qNode.add(curNode.right);
                qSum.add(curSum-curNode.val);
            }
        }
        return false;
        
    }
    

    }

    Stack:

    public class Solution {
    //stack
    public boolean hasPathSum(TreeNode root, int sum) {
        Stack<TreeNode> sNode=new Stack<TreeNode>();
        Stack<Integer> sSum=new Stack<Integer>();
        
        if (root==null) return false;
        sNode.push(root);
        sSum.push(sum);
        while(!sNode.isEmpty()) {
            TreeNode node=sNode.pop();
            int curSum=sSum.pop();
            
            if (node.left==null && node.right==null && node.val==curSum) return true;
            if (node.left!=null) {
                sNode.push(node.left);
                sSum.push(curSum-node.val);
            }
            if(node.right!=null) {
                sNode.push(node.right);
                sSum.push(curSum-node.val);
            }
        }
        return false;
        }
    }

Log in to reply
 

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