最常見的二叉樹面試問題和答案 [針對新手和有經驗者]

介紹

數據結構是面向對象編程中最基本的概念之一。 簡單地說，數據結構是一種在計算機中組織數據的特殊方式，以便對其進行有效處理。 有幾種數據結構，如堆棧、隊列和樹，它們都有自己獨特的屬性。

樹允許我們以分層方式組織數據。 這種數據結構與鍊錶或數組等線性數據結構非常不同。 樹由攜帶信息的節點組成。

二叉樹是一種特殊類型的樹，最多只能有兩個孩子。 這意味著二叉樹中的特定節點可以沒有孩子、一個孩子或兩個孩子，但不能有更多。 二叉樹是一種重要的數據結構，可以幫助我們解決難題並構建複雜的代碼。

如果你申請的是 Java 開發人員或軟件工程師的工作，你的面試可能會包含幾個圍繞這個概念的問題。 通常，候選人發現很難回答基於二叉樹、二叉搜索樹和相關程序的問題。 在本文中，我們將探討一些與二叉樹相關的最常見的面試問題。 本文將幫助您更好地理解這個概念並為您做好準備，以便您找到夢想的工作！

頂級二叉樹面試問答

以下部分包含基於二叉樹概念的問題目錄及其預期答案。

1）什麼是葉節點？

二叉樹或沒有任何子節點的樹中的任何節點都稱為葉節點。

2) 什麼是根節點？

樹中的第一個節點或頂部節點稱為根節點。

3) 如何在 Java 中找到二叉樹的最低共同祖先 (LCA)？

讓我們考慮作為二叉樹一部分的兩個節點 n1 和 n2。

n1 和 n2 的最低共同祖先 (LCA) 是距根最遠的 n1 和 n2 的共享祖先。

您可以按照以下方法查找 LCA。

1. a) 找到從根節點到 n1 的路徑並將其存儲在一個數組中。
2. b) 找到從根節點到 n2 的路徑並將其存儲在一個數組中。
3. c) 遍歷兩條路徑，直到兩個數組中的值相同。

4）如何檢查給定的二叉樹是否是另一棵二叉樹的子樹？

假設我們有一棵二叉樹 T。我們現在要檢查二叉樹 S 是否是 T 的子樹。

為此，首先，嘗試檢查是否在 T 中找到了也在 S 中的節點。

找到這個公共節點後，檢查以下節點是否也是 S 的一部分。

如果是，我們可以有把握地說 S 是 T 的子樹。

必讀：數據結構項目的想法和主題

5）如何找到二叉樹中兩個節點之間的距離？

考慮作為二叉樹一部分的兩個節點 n1 和 n2。

n1 和 n2 之間的距離等於從一個節點到另一個節點需要遍歷的最小邊數。

請務必注意，您遍歷節點之間的最短距離。

6）什麼是二叉搜索樹？

二叉搜索樹 (BST) 是一種特殊類型的二叉樹，其中每個內部節點都包含一個鍵。 對於二叉搜索樹，規則是：

1. a) 一個節點可以有一個大於該節點左子樹中所有鍵的鍵。
2. b) 一個節點可以有一個小於該節點右子樹中所有鍵的鍵。

因此，如果 n1 是一個鍵為 8 的節點，那麼 n1 的左子樹中的每個節點都將包含小於 8 的鍵，並且 n1 的右子樹中的每個節點都將包含大於 8 的鍵。

7) 什麼是自平衡樹？

當發生插入和刪除等操作時，自平衡二叉搜索樹會自動保持其高度盡可能小。

要使 BST 自平衡，重要的是它始終遵循 BST 的規則，以便左子樹具有低值鍵，而右子樹具有高值鍵。

這是通過兩個操作完成的：

- 左旋轉

– 右旋轉

8) 什麼是 AVL 樹？

AVL 樹以其發明者的名字命名：Adelson、Velski 和 Landis。 AVL 樹是一種自平衡二叉樹，它檢查其左子樹和右子樹的高度，並確保差不大於 1。這種差稱為平衡因子

因此，BalanceFactor = 高度（左子樹）-高度（右子樹）

如果平衡因子大於 1，則使用以下一些技術平衡樹：

- 左旋轉

– 右旋轉

- 左右旋轉

– 左右旋轉

另請閱讀：數據結構中的排序

9) 如何在 Java 中將二叉樹轉換為二叉搜索樹？

二叉樹和二叉搜索樹之間的主要區別在於，BST 遵循左子樹應該具有較低的鍵值，而右子樹應該具有較高的鍵值規則。 這可以使用一系列遍歷技術來完成，如下所示：

1. 創建一個臨時數組，存儲樹的中序遍歷
2. 對臨時數組進行排序。 您可以在此處使用任何排序算法。
3. 再次對樹執行中序遍歷。
4. 將數組元素一一複製到每個樹節點。

10) 如何從 Java 中的二叉搜索樹中刪除一個節點？

BST 的刪除操作可能很棘手，因為它的屬性需要在操作後保留。 以下是所有三種可能的情況：

1. 要刪除的節點是葉子節點。
   只需刪除節點。
2. 要刪除的節點有一個孩子。

在這種情況下，將子節點複製到節點並刪除子節點。

1. 要刪除的節點有兩個孩子。

在這種情況下，找到節點的中序後繼。 然後，您可以將其內容複製到節點並刪除中序後繼。

11) 什麼是紅黑樹數據結構？

紅黑樹是一種特殊類型的自平衡樹，具有以下特性：

1. 每個節點都有紅色或黑色的顏色。
2. 根總是黑色的。
3. 紅色節點不能有紅色父節點或紅色子節點。
4. 從根節點到 NULL 節點的每條路徑都有相同數量的黑色節點。

必讀：數據結構項目的想法和主題

12) 你如何判斷兩棵樹是否相同？

如果兩個二叉樹具有相同的數據和排列，則它們是相同的。 這可以通過遍歷兩棵樹並比較它們的數據和排列來完成。

這是可以使我們做到這一點的算法：

1. 檢查根節點的數據（tree1 data ==tree2 data）
2. 遞歸檢查左子樹。 調用sameTree（tree1->左子樹，tree2->左子樹）
3. 同樣，檢查右子樹
4. 如果 a,b,c 為真，則返回 1

結帳：二叉樹的類型

最後的想法

在本文中，我們探討了一些最常見的二叉搜索樹面試問題。 探索更多關於數據結構的知識可以幫助你更好地掌握邏輯和編程。 您可以嘗試查看本文中提到的示例，並通過更改值來構建您的基礎來練習。 通過一些練習，您將能夠很好地完成面試。

如果您想了解數據科學，請查看 IIIT-B 和 upGrad 的數據科學執行 PG 計劃，該計劃是為在職專業人士創建的，提供 10 多個案例研究和項目、實用的實踐研討會、與行業專家的指導、1與行業導師一對一，400 多個小時的學習和頂級公司的工作協助。