在Java的面試中,二叉樹(shù)的遍歷是一個(gè)常見(jiàn)的算法主題。本文將介紹一道經(jīng)典的Java面試題——二叉樹(shù)的后序遍歷,并提供詳細(xì)的解析和解題思路。
題目
給定一個(gè)二叉樹(shù),按照后序遍歷的順序輸出節(jié)點(diǎn)的值。
解析與解題思路
二叉樹(shù)的后序遍歷是一種常見(jiàn)的樹(shù)遍歷方式,可以使用遞歸或迭代的方式來(lái)實(shí)現(xiàn)。
- 遞歸解法:如果二叉樹(shù)為空,則返回。首先遞歸地后序遍歷當(dāng)前節(jié)點(diǎn)的左子樹(shù)。然后遞歸地后序遍歷當(dāng)前節(jié)點(diǎn)的右子樹(shù)。輸出當(dāng)前節(jié)點(diǎn)的值。
- 迭代解法(使用棧):創(chuàng)建一個(gè)棧,并將根節(jié)點(diǎn)入棧。初始化一個(gè)指針current指向根節(jié)點(diǎn),用于記錄當(dāng)前訪(fǎng)問(wèn)的節(jié)點(diǎn)。初始化一個(gè)指針lastVisited指向null,用于記錄上次訪(fǎng)問(wèn)的節(jié)點(diǎn)。當(dāng)棧不為空時(shí),重復(fù)以下步驟:將棧頂節(jié)點(diǎn)的左子樹(shù)依次入棧,直到左子樹(shù)為空。獲取棧頂節(jié)點(diǎn),但不彈出。如果棧頂節(jié)點(diǎn)的右子樹(shù)為空,或者上次訪(fǎng)問(wè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); // 遞歸地后序遍歷左子樹(shù)
postorderTraversal(root.right); // 遞歸地后序遍歷右子樹(shù)
System.out.print(root.val + " "); // 輸出當(dāng)前節(jié)點(diǎn)的值
}
public static void main(String[] args) {
/*
* 構(gòu)造二叉樹(shù):
* 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é)論
通過(guò)遞歸或迭代的方式,我們可以實(shí)現(xiàn)二叉樹(shù)的后序遍歷。掌握了解題思路和實(shí)現(xiàn)代碼,我們能夠在面試中更加自信地回答相關(guān)問(wèn)題。
學(xué)java,就到java編程獅!