[Accepted] java iteration solution with one stack without change the value of TreeNode


  • 2
    S

    Enjoy my first post ^ ^

    public boolean hasPathSum(TreeNode root, int sum) {
    	Stack<TreeNode> stack = new Stack<>();
    	while (!stack.isEmpty() || root != null) {
    		while (root != null) {
    			stack.push(root);
    			sum -= root.val;
    			root = root.left;
    		}
    		
    		if (sum == 0 && stack.peek().right == null && stack.peek().left == null) {
    			return true;
    		} 
    		
    		//root == null
    		//pop all nodes whose children pathes have been both checked.
    		while (!stack.isEmpty() && stack.peek().right == root) {
    		    root = stack.pop();
    		    sum += root.val;
    		}
    		root = stack.isEmpty() ? null : stack.peek().right;
    		//root is now the first node in in-order which has never been pushed in the stack.
    	}
    	return false;
    }

Log in to reply
 

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