阿里面試

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

吉林網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián)公司,吉林網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為吉林上1000+提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站建設(shè)要多少錢(qián)，請(qǐng)找那個(gè)售后服務(wù)好的吉林做網(wǎng)站的公司定做！

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

所以有利用給王二Dog講解二叉樹(shù)的機(jī)會(huì)，我整體梳理了下二叉樹(shù)常見(jiàn)的面試點(diǎn)，發(fā)出來(lái)供大家一起交流學(xué)習(xí)。希望對(duì)你的面試有所幫助。

二叉樹(shù)

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

常見(jiàn)類(lèi)型的二叉樹(shù)是二叉搜索樹(shù)，其中每個(gè)節(jié)點(diǎn)的值大于或等于左子節(jié)點(diǎn)值，并且小于或等于右子節(jié)點(diǎn)中的節(jié)點(diǎn)值。

這是這種二叉樹(shù)的直觀表示：

對(duì)于實(shí)現(xiàn)，我們將使用 Node 類(lèi)來(lái)存儲(chǔ) int 值并保存對(duì)每個(gè)子節(jié)點(diǎn)的引用：

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

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

然后，讓我們添加樹(shù)的根節(jié)點(diǎn)，通常稱(chēng)為 根：

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

讓我們一起來(lái)實(shí)現(xiàn)下

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

插入元素

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

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

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

首先，我們將創(chuàng)建一個(gè)遞歸方法來(lái)進(jìn)行插入：

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;
}

接下來(lái)，我們將創(chuàng)建一個(gè)遞歸方法來(lái)創(chuàng)建根節(jié)點(diǎn)：

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

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

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)在讓我們添加一個(gè)方法來(lái)檢查樹(shù)是否包含特定值。

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

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);
}

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

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

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

現(xiàn)在，讓我們創(chuàng)建一個(gè)簡(jiǎn)單的測(cè)試來(lái)驗(yàn)證樹(shù)真的包含插入的元素：

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

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

刪除元素

另一種常見(jiàn)操作是從樹(shù)中刪除節(jié)點(diǎn)。

首先，我們必須以與之前類(lèi)似的方式找到要?jiǎng)h除的節(jié)點(diǎn)：

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ǎng)h除的節(jié)點(diǎn)，就有3種主要的不同情況：

• 節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)-這是最簡(jiǎn)單的情況; 我們只需要在其父節(jié)點(diǎn)中用 null 替換此節(jié)點(diǎn)
• 節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)-在父節(jié)點(diǎn)中，我們用它唯一的子節(jié)點(diǎn)替換該節(jié)點(diǎn)。
• 節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)- 這是最復(fù)雜的情況，因?yàn)樗枰獦?shù)重組

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

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

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

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

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

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

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

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

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

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)換樹(shù)

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

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

深度優(yōu)先搜索

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

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

in-order：首先訪問(wèn)左子樹(shù)，然后訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)：

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

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

3 4 5 6 7 8 9

pre-order：首先訪問(wèn)根節(jié)點(diǎn)，然后是左子樹(shù)，最后是右子樹(shù)：

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

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

6 4 3 5 8 7 9

post-order：訪問(wèn)左子樹(shù)，右子樹(shù)，最后訪問(wèn)根節(jié)點(diǎn)：

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

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

3 5 4 7 9 8 6

廣度優(yōu)先搜索

這是另一種常見(jiàn)的遍歷類(lèi)型，它在展示進(jìn)入下一級(jí)別之前訪問(wèn)級(jí)別的所有節(jié)點(diǎn)。

這種遍歷也稱(chēng)為按級(jí)別順序，并從根開(kāi)始，從左到右訪問(wèn)樹(shù)的所有級(jí)別。

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

public void traverseLevelOrder() {
    if (root == null) {
        return;
    }
    Queue 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é)點(diǎn)的順序?qū)⑹牵?/p>

6 4 8 3 5 7 9

最后

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

“不積跬步，無(wú)以至千里”，希望未來(lái)的你能成為：有夢(mèng)為馬 隨處可棲！加油，少年！