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

• 后续非递归遍历核心：如果一个节点存在右子树，并且前一个遍历的节点就是右子树节点，才可以遍历当前节点；否则(右子树存在，且没有被遍历)，则遍历右子树。
• 其他部分和前序、中序遍历模板一样。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        List<Integer> list = new ArrayList<>();

        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        TreeNode pre = null;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.offerLast(cur);
                cur = cur.left;  // 左
            }
            cur = stack.peekLast();
            if(cur.right != null && pre != cur.right){ // 右子树存在，且没有被遍历
                cur = cur.right; // 右
            } else { //右子树已经被遍历
                cur = stack.pollLast(); // 根
                list.add(cur.val);
                pre = cur; // 前一个遍历的节点
                cur = null; // 根已经遍历，置空避免判断内层的while
            }
        }
        
        int[] res = new int[list.size()];
        int i = 0;
        for(Integer val : list){
            res[i++] = val;
        }
        return res;
    }
}