阿里第二輪面試：手寫Java二叉樹

阿里面試

現(xiàn)在很多公司在招聘開發(fā)崗位的時候，都會事先在招聘信息中注明面試者應(yīng)當(dāng)具備的知識技能，而且在面試的過程中，有部分對于技能掌握程度有嚴(yán)格要求的公司還會要求面試者手寫代碼，這個環(huán)節(jié)很考驗面試者的基礎(chǔ)功底和實力！

這不，前些天一個朋友去阿里面試的時候，在二面過程中就被要求使用Java實現(xiàn)二叉樹，王二Dog由于沒有準(zhǔn)備這方面的知識，沒有答上來，然后就讓回家等通知了。

所以有利用給王二Dog講解二叉樹的機會，我整體梳理了下二叉樹常見的面試點，發(fā)出來供大家一起交流學(xué)習(xí)。希望對你的面試有所幫助。

二叉樹

二叉樹是遞歸數(shù)據(jù)結(jié)構(gòu)，其中每個節(jié)點最多可以有2個子節(jié)點。

常見類型的二叉樹是二叉搜索樹，其中每個節(jié)點的值大于或等于左子節(jié)點值，并且小于或等于右子節(jié)點中的節(jié)點值。

這是這種二叉樹的直觀表示：

對于實現(xiàn)，我們將使用 Node 類來存儲 int 值并保存對每個子節(jié)點的引用：

class Node {
    int value;//本節(jié)點的值
    Node left;//左邊的子節(jié)點
    Node right;//右邊的子節(jié)點

    Node(int value) {
        this.  value = value;
        right = null;
        left = null;
    }
}

然后，讓我們添加樹的根節(jié)點，通常稱為 根：

public class BinaryTree {
    Node root;
    // ...}

讓我們一起來實現(xiàn)下

現(xiàn)在，讓我們看看可以在二叉樹上執(zhí)行的最常見操作有哪些？

插入元素

我們要介紹的第一個操作是插入新節(jié)點。

首先，我們必須找到我們想要添加新節(jié)點的位置，以便對樹進行排序。我們將從根節(jié)點開始遵循這些規(guī)則：

• 如果新節(jié)點的值低于當(dāng)前節(jié)點的值，我們轉(zhuǎn)到左子節(jié)點
• 如果新節(jié)點的值大于當(dāng)前節(jié)點的值，我們將轉(zhuǎn)到右子節(jié)點
• 節(jié)點當(dāng)前為null時，我們已到達葉節(jié)點，我們可以在該位置插入新節(jié)點

首先，我們將創(chuàng)建一個遞歸方法來進行插入：

private Node addRecursive(Node current, int value) {
    if (current == null) {
        return new Node(value);
    }
    if (value < current.value) {
        current.left = addRecursive(current.left, value);
    } else if (value > current.value) {
        current.right = addRecursive(current.right, value);
    } else {
        // value already exists
        return current;    
    }    
    return current;
}

接下來，我們將創(chuàng)建一個遞歸方法來創(chuàng)建根節(jié)點：

public void add(int value) {
    root = addRecursive(root, value);
}

現(xiàn)在讓我們看看如何使用此方法從我們的示例中創(chuàng)建樹：

private BinaryTree createBinaryTree() {
    BinaryTree bt = new BinaryTree();

    bt.add(6);
    bt.add(4);
    bt.add(8);
    bt.add(3);
    bt.add(5);
    bt.add(7);
    bt.add(9);

    return bt;
}

查找元素

現(xiàn)在讓我們添加一個方法來檢查樹是否包含特定值。

和以前一樣，我們首先創(chuàng)建一個遍歷樹的遞歸方法：

private boolean containsNodeRecursive(Node current, int value) {
    if (current == null) {
        return false;
    }
    if (value == current.value) {
        return true;
    }
    return value < current.value
      ? containsNodeRecursive(current.left, value)
      : containsNodeRecursive(current.right, value);
}

在這里，我們通過將其與當(dāng)前節(jié)點中的值進行比較來搜索該值，然后根據(jù)該值繼續(xù)在左或右子節(jié)點中繼續(xù)查找。

接下來，我們讓創(chuàng)建一個公共方法來查找：

public boolean containsNode(int value) {
    return containsNodeRecursive(root, value);
}

現(xiàn)在，讓我們創(chuàng)建一個簡單的測試來驗證樹真的包含插入的元素：

@Test
public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements() {
    BinaryTree bt = createBinaryTree();

    assertTrue(bt.containsNode(6));
    assertTrue(bt.containsNode(4));
    assertFalse(bt.containsNode(1));
}

刪除元素

另一種常見操作是從樹中刪除節(jié)點。

首先，我們必須以與之前類似的方式找到要刪除的節(jié)點：

private Node deleteRecursive(Node current, int value) {
    if (current == null) {
        return null;
    }
    if (value == current.value) {
        // Node to delete found
        // ... code to delete the node will go here
    }
    if (value < current.value) {
        current.left = deleteRecursive(current.left, value);
        return current;
    }
    current.right = deleteRecursive(current.right, value);
    return current;
}

一旦我們找到要刪除的節(jié)點，就有3種主要的不同情況：

• 節(jié)點沒有子節(jié)點 -這是最簡單的情況; 我們只需要在其父節(jié)點中用 null 替換此節(jié)點
• 節(jié)點只有一個子節(jié)點 -在父節(jié)點中，我們用它唯一的子節(jié)點替換該節(jié)點。
• 節(jié)點有兩個子節(jié)點 - 這是最復(fù)雜的情況，因為它需要樹重組

讓我們看看當(dāng)節(jié)點是葉節(jié)點時我們?nèi)绾螌崿F(xiàn)第一種情況：

if (current.left == null && current.right == null) {
    return null;
}

現(xiàn)在讓我們繼續(xù)討論節(jié)點有一個子節(jié)點的情況：

if (current.right == null) {
    return current.left;
}
if (current.left == null) {
    return current.right;
}

在這里，我們返回 非null 子節(jié)點，以便將其分配給父節(jié)點。

最后，我們必須處理節(jié)點有兩個子節(jié)點的情況。

首先，我們需要找到將替換已刪除節(jié)點的節(jié)點。我們將使用節(jié)點的最小節(jié)點刪除右側(cè)子樹：

private int findSmallestValue(Node root) {
    return root.left == null ? root.value : findSmallestValue(root.left);
}

然后，我們將最小值分配給要刪除的節(jié)點，之后，我們將從右側(cè)子樹中刪除它：

int smallestValue = findSmallestValue(current.right);
current.value = smallestValue;
current.right = deleteRecursive(current.right, smallestValue);
return current;

最后，我們讓創(chuàng)建刪除的公共方法：

public void delete(int value) {
    root = deleteRecursive(root, value);
}

現(xiàn)在，讓我們檢查刪除是否按預(yù)期工作：

@Test
public void givenABinaryTree  () {
    BinaryTree bt = createBinaryTree();

    assertTrue(bt.containsNode(9));
    bt.delete(9);
    assertFalse(bt.containsNode(9));
}

轉(zhuǎn)換樹

在此，我們將看到遍歷樹的不同方式，詳細(xì)介紹深度優(yōu)先和廣度優(yōu)先搜索。

我們將使用之前使用的相同樹，并且我們將顯示每個案例的遍歷順序。

深度優(yōu)先搜索

深度優(yōu)先搜索是一種在每個子節(jié)點探索下一個兄弟之前盡可能深入的遍歷。

有幾種方法可以執(zhí)行深度優(yōu)先搜索：in-order, pre-order 和 post-order。

in-order：首先訪問左子樹，然后訪問根節(jié)點，最后訪問右子樹：

public void traverseInOrder(Node node) {
    if (node != null) {
        traverseInOrder(node.left);
        System.out.print(" " + node.value);
        traverseInOrder(node.right);
    }
}

如果我們調(diào)用此方法，控制臺輸出：

3 4 5 6 7 8 9

pre-order：首先訪問根節(jié)點，然后是左子樹，最后是右子樹：

public void traversePreOrder(Node node) {
    if (node != null) {
        System.out.print(" " + node.value);
        traversePreOrder(node.left);
        traversePreOrder(node.right);
    }
}

如果我們調(diào)用此方法，控制臺輸出：

6 4 3 5 8 7 9

post-order：訪問左子樹，右子樹，最后訪問根節(jié)點：

public void traversePostOrder(Node node) {
    if (node != null) {
        traversePostOrder(node.left);
        traversePostOrder(node.right);
        System.out.print(" " + node.value);
    }
}

如果我們調(diào)用此方法，控制臺輸出：

3 5 4 7 9 8 6

廣度優(yōu)先搜索

這是另一種常見的遍歷類型，它在展示進入下一級別之前訪問級別的所有節(jié)點。

這種遍歷也稱為按級別順序，并從根開始，從左到右訪問樹的所有級別。

對于實現(xiàn)，將我們使用 隊列 按順序保存每個級別的節(jié)點。我們將從列表中提取每個節(jié)點，打印其值，然后將其子節(jié)點添加到隊列中：

public void traverseLevelOrder() {
    if (root == null) {
        return;
    }
    Queue<Node> nodes = new LinkedList<>();
    nodes.add(root);
    while (!nodes.isEmpty()) {
        Node node = nodes.remove();
        System.out.print(" " + node.value);
        if (node.left != null) {
            nodes.add(node.left);
        }
        if (node.right!= null) {
            nodes.add(node.right);
        }
    }
}

在這種情況下，節(jié)點的順序?qū)⑹牵?/p>

6 4 8 3 5 7 9

最后

在本文中，我們已經(jīng)了解了如何在Java中實現(xiàn)已排序的二叉樹及其最常見的操作。你是否從中有所收獲呢？哪怕你能收獲一點點心得，我在此也欣慰了！

“不積跬步，無以至千里”，希望未來的你能成為：有夢為馬 隨處可棲！加油，少年！