A Iterative PostOrder Traversal Java Solution!


  • 0
    L

    public boolean isBalanced(TreeNode root) {
    if (root == null)
    return true;
    if (getHeight(root) == -1)
    return false;
    return true;
    }

    public int getHeight(TreeNode root) {
    	Deque<TreeNode> stack = new LinkedList<TreeNode>();
    	if (root == null)
    		return 0;
    	TreeNode p = root;
    	while (p != null || stack.peekFirst() != null) {
    		while (p != null) {
    			stack.addFirst(p);
    			p = p.left;
    		}
    		TreeNode q = null;
    		boolean flag = true;
    
    		while (stack.peekFirst() != null && flag) {
    			if (q == stack.peekFirst().right) {
    				q = stack.removeFirst();
    				if (q.left == null && q.right == null)
    					q.val = 1;
    				else if (q.left == null && q.right != null) {
    					if (q.right.val > 1)
    						return -1;
    					q.val = q.right.val + 1;
    				} else if (q.left != null && q.right == null) {
    					if (q.left.val > 1)
    						return -1;
    					q.val = q.left.val + 1;
    				} else {
    					if (Math.abs(q.left.val - q.right.val) > 1)
    						return -1;
    				q.val =  Math.max(q.left.val,q.right.val) + 1;
    				}
    			} else {
    				p = stack.peekFirst().right;
    				flag = false;
    			}
    		}
    	}
    	return root.val;
    }

Log in to reply
 

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