Java Iterative Solution via Post-order Tranverse


  • 0

    The recursive solution is a little bit trivial so I tries developing a iterative solution. It turns out that the iterative solution is just a variant of a post-order traversal. I simply modified the solution from the problem about how to do post-order tree transverse and it works well.

    public class Solution {
        public TreeNode invertTree(TreeNode root) {
            
            TreeNode curr = root, prev = null;
            Deque<TreeNode> stack = new LinkedList<TreeNode>();
            
            while ( curr != null || !stack.isEmpty() ) {
                if ( curr != null ) {
                    stack.push(curr);
                    curr = curr.left;
                } else {
                    TreeNode peek = stack.peek();
                    if ( peek.right != null && peek.right != prev ) {
                        curr = peek.right;  
                    } else {
                        swapBranch(peek);
                        prev = stack.pop();
                    }
                } 
            }
            return root;
        }
        
        public void swapBranch(TreeNode node) {
            TreeNode tmp = node.left;
            node.left = node.right; node.right = tmp;
        }
    }

Log in to reply
 

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