68.二叉树的后序遍历

描述

给出一棵二叉树，返回其节点值的后序遍历。

样例

给出一棵二叉树 {1,#,2,3},

   1
    \
     2
    /
   3

返回 [3,2,1]

挑战

你能使用非递归实现么？

代码

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

1. 非递归 (重点)
   思路

对于二叉树
             1
           /   \
         2      3
       /   \   /  \
      4     5 6    7

后序遍历输出顺序为 4 5 2 6 7 3 1

curr 代表当前访问的结点
prev 代表访问的上一结点

首先要先向下从根结点 1 开始向下寻找，此时 prev = null，curr = 1
此时 prev = null 满足 if (prev == null || prev.left == curr || prev.right == curr)条件，将 1 的左儿子 2 加入栈，此时 prev = 1， curr = 2
此时 prev.left = curr 满足 if (prev == null || prev.left == curr || prev.right == curr) 条件，将 2 的左儿子 4 加入栈， prev = 2， curr = 4
此时 prev.left = curr 满足 if (prev == null || prev.left == curr || prev.right == curr) 条件， 但 4 不存在子结点，prev = 4，curr = 4
此时不满足前两个 if 判断条件，将 4 作为整颗二叉树的第一个结点，将值加入 results，同时把值已经加入 results 的结点从栈里
pop 掉
因为 curr 总指向栈顶元素，所以进入下一轮 while 循环时 prev = 4， curr = 2，此时满足第二个else if (curr.left == prev)判断条件，将 2 的右儿子加入栈，栈顶元素变为 5
当进入下一轮 while 循环时，prev = 2， curr = 5，由于满足 if (prev == null || prev.left == curr || prev.right == curr) 条件，会继续向下查找，此时分为两种情况：

1. 如果此时 5 为叶子结点没有儿子则 prev = 5， curr = 5，则会满足第三个 if 条件，进行将 5 的值加入 results，同时 将 5 从栈中移除，然后下一轮 while 循环 prev = 5， curr = 2，会把 2 的值加入 results，然后从栈中移除 2；
2. 如果 5 不是叶子结点，可以对以 5 为根结点的二叉树执行重复操作，寻找该二叉树的最左结点作为整个二叉树的第二个结点，直到将以 5 为根结点的二叉树全部处理完

左子树开始了回溯，其余结点的执行过程依次类推，直到执行到根结点的左儿子，下一步按同样方法处理根结点右子树，最后处理根结点

public class Solution {
    /*
     * @param root: A Tree
     * @return: Postorder in ArrayList which contains node values.
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode prev = null; 
        /* curr 指针指向当前访问的结点，它一直指向栈顶结点
         * 每次出栈一个结点后，将其重新置为栈顶结点
         */
        TreeNode curr = root;
    
        if (root == null) {
            return result;
        }
        
        // 根结点压入到栈底最后处理
        stack.push(root);
        // 栈为空时结束循环
        while (!stack.empty()) {
            // 将当前结点置为栈顶结点
            curr = stack.peek();
            
            // 从上往下
            if (prev == null || prev.left == curr || prev.right == curr) {
                // 注意此处是 if else,只执行一句,写成两个 if 会报错
                // 从上往下只朝一个方向前进
                if (curr.left != null) {
                    stack.push(curr.left);
                } else if (curr.right != null) {
                    stack.push(curr.right);
                }
             
            // 从下往上   
            // 当结点左儿子已经输出，访问右儿子
            } else if (curr.left == prev) {
                if (curr.right != null) {
                    stack.push(curr.right);
                }
            // 当前结点是叶子结点或结点的左右儿子已经输出
            } else {
                result.add(curr.val);
                // 栈顶元素从栈中弹出，更新 curr 指向
                stack.pop();
            }
            /* 最后的访问结点变成当前结点，while 进入下一轮循环，
             * 当前元素会在 while 初始化处重新指向栈顶结点
             */
            prev = curr;
        }
    
        return result;
    }
}

2. 分治 + 递归

public class Solution {
    /*
     * @param root: A Tree
     * @return: Postorder in ArrayList which contains node values.
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> results = new ArrayList<>();
        
        if (root == null) {
            return results;
        }
        
        List<Integer> left = postorderTraversal(root.left);
        List<Integer> right = postorderTraversal(root.right);
        
        results.addAll(left);
        results.addAll(right);
        results.add(root.val);
        
        return results;
    }
}

3. 遍历 + 递归

public class Solution {
    /*
     * @param root: A Tree
     * @return: Postorder in ArrayList which contains node values.
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> results = new ArrayList<>();
        
        traversal(root, results);
        return results;
    }
    
    private void traversal(TreeNode root, List<Integer> results) {
        if (root == null) {
            return;
        }
        
        traversal(root.left, results);
        traversal(root.right, results);
        results.add(root.val);
    }
}