java solution


  • 0
    C
     import java.util.*;
      public class Solution {
    	public boolean isParent(TreeNode n1,TreeNode n2)
    {
    	return n1.left == n2 || n1.right == n2;
    }
    
    public boolean hasPathSum(TreeNode root, int sum) {
    	
    	if(root == null)
    		return false;
    	
    	Stack<TreeNode> nodes = new Stack<TreeNode>();
    	Stack<Integer> current_sum = new Stack<Integer>();
    	
    	nodes.push(root);
    	current_sum.push(root.val);
    	
    	while(!nodes.isEmpty())
    	{
    		TreeNode tmpNode = nodes.peek();
    		int sum_node = current_sum.peek();
    		
    		if(tmpNode.left == null && tmpNode.right == null)
    		{
    			if(sum_node == sum)
    				return true;
    			
    			TreeNode pop = nodes.pop();
    			current_sum.pop();
    			
    			while(!nodes.isEmpty() && isParent(nodes.peek(),pop))
    			{
    				pop = nodes.pop();
    				current_sum.pop();
    			}
    			continue;
    		}
    		int current = current_sum.peek();
    		if(tmpNode.left != null)
    		{
    			nodes.push(tmpNode.left);
    			current_sum.push(current+tmpNode.left.val);	
    		}
    		
    		if(tmpNode.right != null)
    		{
    			nodes.push(tmpNode.right);
    			current_sum.push(current+tmpNode.right.val);
    		}
    	}
    	return false;
    }
    

    }


Log in to reply
 

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