[LeetCode]Binary Tree Postorder Traversal

之前在Binary Tree Preorder Traversal中说过，preorder和inorder的方法不适于Postorder因为不方便模拟第三次对节点的访问，所以只好改变方法。



首先把代码贴出来，然后详细讲解：

	/**
	* 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> res = new ArrayList<Integer>();
	if (root == null)
	return res;
	Stack<TreeNode> stack = new Stack<TreeNode>();
	TreeNode pre = null;
	stack.push(root);
	while(!stack.isEmpty()) {
	TreeNode curr = stack.peek();
	if (isLeaf(curr) || (pre != null && (pre == curr.left || pre == curr.right))) {
	res.add(stack.pop().val);
	pre = curr;
	}
	else {
	if (curr.right != null)
	stack.push(curr.right);
	if (curr.left != null)
	stack.push(curr.left);
	}
	}
	return res;
	}
	private boolean isLeaf(TreeNode node) {
	return node.left == null && node.right == null;
	}
	}

view raw bst postorder.java hosted with ❤ by GitHub

首先把root push近stack里，之后只要stack不为空就进入循环。首先定义pre来表示我们之前访问的节点，这个作用是用来判断我们应不应该pop出当前节点。当前节点为stack.peek()获得的节点，如果这个节点之前没有访问过，我们依次push 右子节点和左子节点，这样做是保证左子结点在栈顶(24 - 29行)。如果是叶节点或者是第二次访问的话，就pop()出来，并且加入结果集，pre设置为当前节点((20 - 23行))。
可以看到我们这样模拟省略了第二次访问节点的情况，第二次的情况是由在栈里左右子节点的相对顺序来模拟的，因为先push右子节点然后左子结点，那么首先会遍历左子树然后才遍历右子树。如果没有左子树或者右子树情况，那么就先遍历另外一个有的子树。这样由于子节点在栈里都在parent的上方，所以一定先访问完子节点再会去访问父节点，保证了算法的正确性。

Follow up: constant space 后序遍历