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

import java.util.*;
public class Solution {
    public int[] postorderTraversal(TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null; // 用于标记当前节点的右孩子是否被访问过
        TreeNode temp = root;
        while (temp != null || !stack.isEmpty()) {
            while (temp != null) {
                stack.push(temp);
                temp = temp.left;
            }
            TreeNode node = stack.pop(); // 当左孩子都压入栈后再依次弹栈
            if (node.right == null || pre == node.right) {
                // 如果该节点没有右孩子或右孩子已经被访问过
                list.add(node.val);
                pre = node;
            } else {
                stack.push(
                    node); // 中间节点还不能输出，得等到右孩子被访问完
                // 访问右孩子
                temp = node.right;
            }
        }
        int len = list.size();
        int[] arr = new int[len];
        for (int i = 0; i < len; i++)
            arr[i] = list.get(i);
        return arr;
    }
}

最难不过坚持