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?

思路：

代码：

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}

public class _145_PostOrderTraverse {
	public List<Integer> postorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root == null)
			return list;
		Stack<TreeNode> st = new Stack<TreeNode>();
		Stack<TreeNode> st1 = new Stack<TreeNode>();
		st.push(root);
		TreeNode top = null;
		while (!st.empty()) {
			top=st.peek();
			while(top.left!=null)//达到页结点
			{
				st.push(top.left);
				top=top.left;
			}
			while(!st.empty())
			{
				top=st.peek();
				if(top.right==null)//无右子树时，访问结点
				{
					list.add(top.val);
					st.pop();
				}else 
				{
					if(st1.empty()||(!st1.empty()&&st1.peek()!=top))//有右子树且第一次出现，将右子树入栈，并将结点在st1中标记一下
					{
						st1.push(top);
						st.push(top.right);
						break;//右子树入栈了，然后从右子树开始
					}
					else//有右子树，但是第二次出现了，访问该结点
					{
						list.add(top.val);
						st1.pop();
						st.pop();
					}
				}
				
			}
		}
		return list;
	}
}

结果：

leetcode_145_Binary Tree Postorder Traversal

原文：http://blog.csdn.net/mnmlist/article/details/44616639