My java no-recursive method


  • 20
    S

    the idea is preorder traverse , instead of using recursive call, I am using a stack.
    the only problem is that I changed TreeNode value

    public boolean hasPathSum(TreeNode root, int sum) {
    	    Stack <TreeNode> stack = new Stack<> ();	    
    	    stack.push(root) ;	    
    	    while (!stack.isEmpty() && root != null){
    	    	TreeNode cur = stack.pop() ;	
    	    	if (cur.left == null && cur.right == null){	    		
    	    		if (cur.val == sum ) return true ;
    	    	}
    	    	if (cur.right != null) {
    	    		cur.right.val = cur.val + cur.right.val ;
    	    		stack.push(cur.right) ;
    	    	}
    	    	if (cur.left != null) {
    	    		cur.left.val = cur.val + cur.left.val;
    	    		stack.push(cur.left);
    	    	}
    	    }	    
    	    return false ;
    	 }

  • 47
    A

    Similar solution as yours. Your solution has changed the internal tree node value, and in production code, this may be not permitted. Followed is my solution:

    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;
        }
    

  • 0
    B

    thanks for this beautiful implementation!


  • 0
    L

    thanks for your sharing


Log in to reply
 

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