Binary Tree Postorder Traversal

用递归的方法是和其他的traversal没有差别
http://watchurspeed.wordpress.com/2014/02/10/binary-tree-level-order-traversal-ii/comment-page-1/#comment-43
如果用iterative的方法的话,和recrisive其实一样,只不过recursive的stack用自己定义的stack代替而已,还有一个hashSet来跟踪visited过的node就好。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> s = new Stack<TreeNode>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        HashSet<TreeNode> visited = new HashSet<TreeNode>();
        if (root == null)
            return result;
        s.push(root);
        visited.add(root);
        while(!s.isEmpty()) {
            if (s.peek().left != null && !visited.contains(s.peek().left)) {// if left never been visited
                visited.add(s.peek().left); // dont reverse these two lines, change s for the last step
                s.push(s.peek().left);
            }
            else if (s.peek().right != null && !visited.contains(s.peek().right)) {
                visited.add(s.peek().right);
                s.push(s.peek().right);
            }
            else
                result.add(s.pop().val);
        }
        return result;
    }
}

No need to have an hashset, just use one TreeNode to keep track of the last visited node, if it is one of the child, then the node has been visited and thus should be poped. Otherwise push it o the stack. The order of the traversal is established by the order the two child node pushed into the stack, so we dont need prev pointer to help when traversing the tree

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (root == null)
            return res;
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode prev = new TreeNode(-1); // node to track the last visited node, should not set to null. 
        s.push(root);
        while(!s.isEmpty()) {
            TreeNode curr = s.peek();
            //if is leaf or any of the two children has been visited
            if ((curr.left == null && curr.right == null) || (prev == curr.right) || (prev == curr.left)) {
                prev = curr;
                res.add(s.pop().val);
            }
            //if eithter children has not been visited
            else {
                if (curr.right != null)
                    s.push(curr.right);
                if (curr.left != null)
                    s.push(curr.left);
            }
        }
        return res;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s