一. 题目

二. 思路

• 后序遍历：左友根

三. 代码

1. 递归

class TreeNode
{
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode()
    {
    }

    TreeNode(int val)
    {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution
{
    final List<Integer> ans = new ArrayList<>();

    void dfs(TreeNode cur)
    {
        if (cur == null) return;
        if (cur.left != null) dfs(cur.left);
        if (cur.right != null) dfs(cur.right);
        ans.add(cur.val);
    }

    public List<Integer> postorderTraversal(TreeNode root)
    {
        ans.clear();
        dfs(root);
        return ans;
    }
}

2. 迭代

class Solution
{
    final List<Integer> ans = new ArrayList<>();
    final Deque<TreeNode> stk = new ArrayDeque<>(110);//栈

    public List<Integer> postorderTraversal(TreeNode root)
    {
        stk.clear();
        ans.clear();
        TreeNode pre = null;//前一个出栈的节点
        while (root != null || !stk.isEmpty())
        {
            while (root != null)//遍历左
            {
                stk.offerLast(root);
                root = root.left;
            }
            root = stk.pollLast();
            if (root.right == null || root.right == pre)//右边是空，或已经遍历过，该遍历根了
            {
                ans.add(root.val);
                pre = root;
                root = null;//该回到上一层了，当前的左右根遍历完了
            } else//右边还没遍历
            {
                stk.offerLast(root);//再次入栈
                root = root.right;
            }
        }

        return ans;
    }
}