My solution of postorder traverse Java


  • 2
    F
    public class Solution {
        public boolean hasPathSum(TreeNode root, int sum){
    		Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
    		Deque<Boolean> flagStack = new ArrayDeque<Boolean>();
    		Deque<Integer> dataStack = new ArrayDeque<Integer>();
    		TreeNode p = root;
    		dataStack.add(sum);
    		while(p != null || stack.size() > 0){
    			while(p != null){
    				stack.add(p);
    				dataStack.add(dataStack.getLast() - p.val);
    				flagStack.add(true);
    				p = p.left;
    			}
    			if(flagStack.peekLast()){
    				p = stack.peekLast().right;
    				flagStack.removeLast();
    				flagStack.add(false);
    			}else{
    				p = stack.removeLast();
    				flagStack.removeLast();
    				if(p.left == null && p.right == null && (int)dataStack.peekLast() == 0)
    					return true;
    				dataStack.removeLast();
    				p = null;
    			}
    		}
    		return false;
    	}
    }

Log in to reply
 

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