[轉(zhuǎn)]一文圖解二叉樹面試題

原文：泥瓦匠-一文圖解二叉樹面試題

二叉樹，搜索二叉樹，是算法面試的必面題。聊聊面試點：

一、樹 & 二叉樹

樹是由節(jié)點和邊構(gòu)成，儲存元素的集合。節(jié)點分根節(jié)點、父節(jié)點和子節(jié)點的概念。
如圖：樹深=4; 5是根節(jié)點；同樣8與3的關(guān)系是父子節(jié)點關(guān)系。

二叉樹binary tree，則加了“二叉”（binary），意思是在樹中作區(qū)分。每個節(jié)點至多有兩個子（child）,left child & right child。二叉樹在很多例子中使用，比如二叉樹表示算術(shù)表達(dá)式。
如圖：1/8是左節(jié)點；2/3是右節(jié)點；

二、二叉搜索樹 BST

顧名思義，二叉樹上又加了個搜索的限制。其要求：每個節(jié)點比其左子樹元素大，比其右子樹元素小。
如圖：每個節(jié)點比它左子樹的任意節(jié)點大，而且比它右子樹的任意節(jié)點小

Java 實現(xiàn)代碼如下：

public class BinarySearchTree {
    /**
     * 根節(jié)點
     */
    public static TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }

    /**
     * 查找
     *      樹深(N) O(lgN)
     *      1\. 從root節(jié)點開始
     *      2\. 比當(dāng)前節(jié)點值小,則找其左節(jié)點
     *      3\. 比當(dāng)前節(jié)點值大,則找其右節(jié)點
     *      4\. 與當(dāng)前節(jié)點值相等,查找到返回TRUE
     *      5\. 查找完畢未找到,
     * @param key
     * @return
     */
    public TreeNode search (int key) {
        TreeNode current = root;
        while (current != null
                && key != current.value) {
            if (key < current.value )
                current = current.left;
            else
                current = current.right;
        }
        return current;
    }

    /**
     * 插入
     *      1\. 從root節(jié)點開始
     *      2\. 如果root為空,root為插入值
     *      循環(huán):
     *      3\. 如果當(dāng)前節(jié)點值大于插入值,找左節(jié)點
     *      4\. 如果當(dāng)前節(jié)點值小于插入值,找右節(jié)點
     * @param key
     * @return
     */
    public TreeNode insert (int key) {
        // 新增節(jié)點
        TreeNode newNode = new TreeNode(key);
        // 當(dāng)前節(jié)點
        TreeNode current = root;
        // 上個節(jié)點
        TreeNode parent  = null;
        // 如果根節(jié)點為空
        if (current == null) {
            root = newNode;
            return newNode;
        }
        while (true) {
            parent = current;
            if (key < current.value) {
                current = current.left;
                if (current == null) {
                    parent.left = newNode;
                    return newNode;
                }
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = newNode;
                    return newNode;
                }
            }
        }
    }

    /**
     * 刪除節(jié)點
     *      1.找到刪除節(jié)點
     *      2.如果刪除節(jié)點左節(jié)點為空 , 右節(jié)點也為空;
     *      3.如果刪除節(jié)點只有一個子節(jié)點 右節(jié)點 或者 左節(jié)點
     *      4.如果刪除節(jié)點左右子節(jié)點都不為空
     * @param key
     * @return
     */
    public TreeNode delete (int key) {
        TreeNode parent  = root;
        TreeNode current = root;
        boolean isLeftChild = false;
        // 找到刪除節(jié)點 及 是否在左子樹
        while (current.value != key) {
            parent = current;
            if (current.value > key) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }

            if (current == null) {
                return current;
            }
        }

        // 如果刪除節(jié)點左節(jié)點為空 , 右節(jié)點也為空
        if (current.left == null && current.right == null) {
            if (current == root) {
                root = null;
            }
            // 在左子樹
            if (isLeftChild == true) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }
        // 如果刪除節(jié)點只有一個子節(jié)點 右節(jié)點 或者 左節(jié)點
        else if (current.right == null) {
            if (current == root) {
                root = current.left;
            } else if (isLeftChild) {
                parent.left = current.left;
            } else {
                parent.right = current.left;
            }

        }
        else if (current.left == null) {
            if (current == root) {
                root = current.right;
            } else if (isLeftChild) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        }
        // 如果刪除節(jié)點左右子節(jié)點都不為空
        else if (current.left != null && current.right != null) {
            // 找到刪除節(jié)點的后繼者
            TreeNode successor = getDeleteSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left;
        }
        return current;
    }

    /**
     * 獲取刪除節(jié)點的后繼者
     *      刪除節(jié)點的后繼者是在其右節(jié)點樹種最小的節(jié)點
     * @param deleteNode
     * @return
     */
    public TreeNode getDeleteSuccessor(TreeNode deleteNode) {
        // 后繼者
        TreeNode successor = null;
        TreeNode successorParent = null;
        TreeNode current = deleteNode.right;

        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.left;
        }

        // 檢查后繼者(不可能有左節(jié)點樹)是否有右節(jié)點樹
        // 如果它有右節(jié)點樹,則替換后繼者位置,加到后繼者父親節(jié)點的左節(jié)點.
        if (successor != deleteNode.right) {
            successorParent.left = successor.right;
            successor.right = deleteNode.right;
        }

        return successor;
    }

    public void toString(TreeNode root) {
        if (root != null) {
            toString(root.left);
            System.out.print("value = " + root.value + " -> ");
            toString(root.right);
        }
    }
}

/**
 * 節(jié)點
 */
class TreeNode {

    /**
     * 節(jié)點值
     */
    int value;

    /**
     * 左節(jié)點
     */
    TreeNode left;

    /**
     * 右節(jié)點
     */
    TreeNode right;

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

面試點一：理解 TreeNode 數(shù)據(jù)結(jié)構(gòu)

節(jié)點數(shù)據(jù)結(jié)構(gòu)，即節(jié)點分左節(jié)點和右節(jié)點及本身節(jié)點值。如圖

面試點二：如何確定二叉樹的最大深度或者最小深度

答案：簡單的遞歸實現(xiàn)即可，代碼如下：

int maxDeath(TreeNode node){
    if(node==null){
        return 0;
    }
    int left = maxDeath(node.left);
    int right = maxDeath(node.right);
    return Math.max(left,right) + 1;
}

    int getMinDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        return getMin(root);
    }
    int getMin(TreeNode root){
        if(root == null){
            return Integer.MAX_VALUE;
        }
        if(root.left == null&&root.right == null){
            return 1;
        }
        return Math.min(getMin(root.left),getMin(root.right)) + 1;
    }

面試點三：如何確定二叉樹是否是平衡二叉樹

答案：簡單的遞歸實現(xiàn)即可，代碼如下：

    boolean isBalanced(TreeNode node){
        return maxDeath2(node)!=-1;
    }
    int maxDeath2(TreeNode node){
        if(node == null){
            return 0;
        }
        int left = maxDeath2(node.left);
        int right = maxDeath2(node.right);
        if(left==-1||right==-1||Math.abs(left-right)>1){
            return -1;
        }
        return Math.max(left, right) + 1;
    }

前面面試點是 二叉樹 的，后面面試點是 搜索二叉樹 的。先運行搜搜二叉樹代碼：

public class BinarySearchTreeTest {

    public static void main(String[] args) {
        BinarySearchTree b = new BinarySearchTree();
        b.insert(3);b.insert(8);b.insert(1);b.insert(4);b.insert(6);
        b.insert(2);b.insert(10);b.insert(9);b.insert(20);b.insert(25);

        // 打印二叉樹
        b.toString(b.root);
        System.out.println();

        // 是否存在節(jié)點值10
        TreeNode node01 = b.search(10);
        System.out.println("是否存在節(jié)點值為10 => " + node01.value);
        // 是否存在節(jié)點值11
        TreeNode node02 = b.search(11);
        System.out.println("是否存在節(jié)點值為11 => " + node02);

        // 刪除節(jié)點8
        TreeNode node03 = b.delete(8);
        System.out.println("刪除節(jié)點8 => " + node03.value);
        b.toString(b.root);

    }
}

結(jié)果如下：

value = 1 -> value = 2 -> value = 3 -> value = 4 -> value = 6 -> value = 8 -> value = 9 -> value = 10 -> value = 20 -> value = 25 -> 
是否存在節(jié)點值為10 => 10
是否存在節(jié)點值為11 => null
刪除節(jié)點8 => 8
value = 1 -> value = 2 -> value = 3 -> value = 4 -> value = 6 -> value = 9 -> value = 10 -> value = 20 -> value = 25 ->

面試點四：搜索二叉樹如何實現(xiàn)插入

插入，和刪除一樣會引起二叉搜索樹的動態(tài)變化。插入相對刪處理邏輯相對簡單些。如圖插入的邏輯：

    1. 從root節(jié)點開始
    1. 如果root為空,root為插入值
    1. 循環(huán):
    1. 如果當(dāng)前節(jié)點值大于插入值,找左節(jié)點
    1. 如果當(dāng)前節(jié)點值小于插入值,找右節(jié)點

面試點五：搜索二叉樹如何實現(xiàn)查找

其算法復(fù)雜度 : O(lgN),樹深(N)。如圖查找邏輯：

image
  1. 從root節(jié)點開始
  2. 比當(dāng)前節(jié)點值小,則找其左節(jié)點
  3. 比當(dāng)前節(jié)點值大,則找其右節(jié)點
  4. 與當(dāng)前節(jié)點值相等,查找到返回TRUE
  5. 查找完畢未找到

面試點五：搜索二叉樹如何實現(xiàn)刪除

比較復(fù)雜了。首先找到刪除節(jié)點，其尋找方法：刪除節(jié)點的后繼者是在其右節(jié)點樹種最小的節(jié)點。如圖刪除對應(yīng)邏輯：

結(jié)果為：

    1. 找到刪除節(jié)點
    1. 如果刪除節(jié)點左節(jié)點為空 , 右節(jié)點也為空
    1. 如果刪除節(jié)點只有一個子節(jié)點 右節(jié)點 或者 左節(jié)點
    1. 如果刪除節(jié)點左右子節(jié)點都不為空

三、小結(jié)

就像碼出高效面試的程序媛偶爾吃一碗“老壇酸菜牛肉面”一樣的味道，品味一個算法，比如 BST 的時候，總是那種說不出的味道。

面試必備小結(jié)：

  • 樹，二叉樹的概念
  • BST 算法
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容