App下載

經(jīng)典Java面試題解析:二叉樹的后序遍歷

夢里花 2023-07-12 09:30:00 瀏覽數(shù) (1750)
反饋

在Java的面試中,二叉樹的遍歷是一個(gè)常見的算法主題。本文將介紹一道經(jīng)典的Java面試題——二叉樹的后序遍歷,并提供詳細(xì)的解析和解題思路。

題目

給定一個(gè)二叉樹,按照后序遍歷的順序輸出節(jié)點(diǎn)的值。

解析與解題思路

二叉樹的后序遍歷是一種常見的樹遍歷方式,可以使用遞歸或迭代的方式來實(shí)現(xiàn)。

  1. 遞歸解法:如果二叉樹為空,則返回。首先遞歸地后序遍歷當(dāng)前節(jié)點(diǎn)的左子樹。然后遞歸地后序遍歷當(dāng)前節(jié)點(diǎn)的右子樹。輸出當(dāng)前節(jié)點(diǎn)的值。
  2. 迭代解法(使用棧):創(chuàng)建一個(gè)棧,并將根節(jié)點(diǎn)入棧。初始化一個(gè)指針current指向根節(jié)點(diǎn),用于記錄當(dāng)前訪問的節(jié)點(diǎn)。初始化一個(gè)指針lastVisited指向null,用于記錄上次訪問的節(jié)點(diǎn)。當(dāng)棧不為空時(shí),重復(fù)以下步驟:將棧頂節(jié)點(diǎn)的左子樹依次入棧,直到左子樹為空。獲取棧頂節(jié)點(diǎn),但不彈出。如果棧頂節(jié)點(diǎn)的右子樹為空,或者上次訪問的節(jié)點(diǎn)是棧頂節(jié)點(diǎn)的右子節(jié)點(diǎn),則彈出棧頂節(jié)點(diǎn)并輸出其值,將lastVisited更新為棧頂節(jié)點(diǎn)。否則,將棧頂節(jié)點(diǎn)的右子節(jié)點(diǎn)入棧,并將current更新為棧頂節(jié)點(diǎn)的右子節(jié)點(diǎn)。

以下是Java代碼實(shí)例(使用遞歸解法):

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 + " "); // 輸出當(dāng)前節(jié)點(diǎn)的值
    }

    public static void main(String[] args) {
        /*
         * 構(gòu)造二叉樹:
         *      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("后序遍歷結(jié)果:");
        postorderTraversal(root);
    }
}

輸出結(jié)果:

后序遍歷結(jié)果:4 5 2 3 1

結(jié)論 

通過遞歸或迭代的方式,我們可以實(shí)現(xiàn)二叉樹的后序遍歷。掌握了解題思路和實(shí)現(xiàn)代碼,我們能夠在面試中更加自信地回答相關(guān)問題。

學(xué)java,就到java編程獅!


0 人點(diǎn)贊