经典Java面试题解析：二叉树的后序遍历

在Java的面试中，二叉树的遍历是一个常见的算法主题。本文将介绍一道经典的Java面试题——二叉树的后序遍历，并提供详细的解析和解题思路。

题目

给定一个二叉树，按照后序遍历的顺序输出节点的值。

解析与解题思路

二叉树的后序遍历是一种常见的树遍历方式，可以使用递归或迭代的方式来实现。

1. 递归解法：如果二叉树为空，则返回。首先递归地后序遍历当前节点的左子树。然后递归地后序遍历当前节点的右子树。输出当前节点的值。
2. 迭代解法（使用栈）：创建一个栈，并将根节点入栈。初始化一个指针current指向根节点，用于记录当前访问的节点。初始化一个指针lastVisited指向null，用于记录上次访问的节点。当栈不为空时，重复以下步骤：将栈顶节点的左子树依次入栈，直到左子树为空。获取栈顶节点，但不弹出。如果栈顶节点的右子树为空，或者上次访问的节点是栈顶节点的右子节点，则弹出栈顶节点并输出其值，将lastVisited更新为栈顶节点。否则，将栈顶节点的右子节点入栈，并将current更新为栈顶节点的右子节点。

以下是Java代码实例（使用递归解法）：

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

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

public class PostorderTraversal {
    public static void postorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        postorderTraversal(root.left); // 递归地后序遍历左子树
        postorderTraversal(root.right); // 递归地后序遍历右子树
        System.out.print(root.val + " "); // 输出当前节点的值
    }

    public static void main(String[] args) {
        /*
         * 构造二叉树：
         *      1
         *     / \
         *    2   3
         *   / \
         *  4   5
         */
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        System.out.print("后序遍历结果：");
        postorderTraversal(root);
    }
}

输出结果：

后序遍历结果：4 5 2 3 1

结论 

通过递归或迭代的方式，我们可以实现二叉树的后序遍历。掌握了解题思路和实现代码，我们能够在面试中更加自信地回答相关问题。

学java，就到java编程狮！