题解 | #二叉树的后序遍历#

/* 这个解法可能是最佳实践，思路清晰，易于理解。
 * 核心思想是用栈做辅助空间，先从根往左一直入栈，直到为空，然后判断栈顶元素的右孩子，如果不为空且未被访问过，
 * 则从它开始重复左孩子入栈的过程；否则说明此时栈顶为要访问的节点（因为左右孩子都是要么为空要么已访问过了），
 * 出栈然后访问即可，接下来再判断栈顶元素的右孩子...直到栈空。
 */
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        TreeNode p = root, r = null;        //P记录当前节点，r用来记录上一次访问的节点
        Stack<TreeNode> s = new Stack<TreeNode>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        while(p != null || !s.isEmpty()) {
            if(p != null) {        //左孩子一直入栈，直到左孩子为空
                s.push(p);
                p = p.left;
            } else {
                p = s.peek();
                p = p.right;
                if(p != null && p != r) {    //如果栈顶元素的右孩子不为空，且未被访问过
                    s.push(p);                //则右孩子进栈，然后重复左孩子一直进栈直到为空的过程
                    p = p.left;
                } else {
                    p = s.pop();            //否则出栈，访问，r记录刚刚访问的节点
                    list.add(p.val);
                    r = p;
                    p = null;
                }
            }
        }
        return list;
    }
}