Sunday, January 11, 2015

LeetCode 145: Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> post = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        
        TreeNode node = root;
        TreeNode peekNode = null;
        TreeNode lastVisitedNode = null;
        
        while (!stack.isEmpty() || node != null)
        {
            if (node != null)
            {
                stack.push(node);
                
                // Left
                node = node.left;
            }
            else
            {
                peekNode = stack.peek();
                
                if (peekNode.right != null && lastVisitedNode != peekNode.right)
                    
                    // Right
                    node = peekNode.right;
                else
                {
                    // Center
                    post.add(peekNode.val);
                    
                    lastVisitedNode = stack.pop();
                }
            }
        }
        
        return post;
    }
}

No comments:

Post a Comment