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

二叉樹彪见，搜索二叉樹，是算法面試的必面題娱挨。聊聊面試點(diǎn)：

一余指、樹 & 二叉樹

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

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

二捞慌、二叉搜索樹 BST

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

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

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

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

    /**
     * 查找
     *      樹深(N) O(lgN)
     *      1\. 從root節(jié)點(diǎn)開始
     *      2\. 比當(dāng)前節(jié)點(diǎn)值小,則找其左節(jié)點(diǎn)
     *      3\. 比當(dāng)前節(jié)點(diǎn)值大,則找其右節(jié)點(diǎn)
     *      4\. 與當(dāng)前節(jié)點(diǎn)值相等,查找到返回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é)點(diǎn)開始
     *      2\. 如果root為空,root為插入值
     *      循環(huán):
     *      3\. 如果當(dāng)前節(jié)點(diǎn)值大于插入值,找左節(jié)點(diǎn)
     *      4\. 如果當(dāng)前節(jié)點(diǎn)值小于插入值,找右節(jié)點(diǎn)
     * @param key
     * @return
     */
    public TreeNode insert (int key) {
        // 新增節(jié)點(diǎn)
        TreeNode newNode = new TreeNode(key);
        // 當(dāng)前節(jié)點(diǎn)
        TreeNode current = root;
        // 上個節(jié)點(diǎn)
        TreeNode parent  = null;
        // 如果根節(jié)點(diǎn)為空
        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é)點(diǎn)
     *      1.找到刪除節(jié)點(diǎn)
     *      2.如果刪除節(jié)點(diǎn)左節(jié)點(diǎn)為空 , 右節(jié)點(diǎn)也為空;
     *      3.如果刪除節(jié)點(diǎn)只有一個子節(jié)點(diǎn) 右節(jié)點(diǎn) 或者 左節(jié)點(diǎn)
     *      4.如果刪除節(jié)點(diǎn)左右子節(jié)點(diǎn)都不為空
     * @param key
     * @return
     */
    public TreeNode delete (int key) {
        TreeNode parent  = root;
        TreeNode current = root;
        boolean isLeftChild = false;
        // 找到刪除節(jié)點(diǎn) 及 是否在左子樹
        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é)點(diǎn)左節(jié)點(diǎn)為空 , 右節(jié)點(diǎn)也為空
        if (current.left == null && current.right == null) {
            if (current == root) {
                root = null;
            }
            // 在左子樹
            if (isLeftChild == true) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }
        // 如果刪除節(jié)點(diǎn)只有一個子節(jié)點(diǎn) 右節(jié)點(diǎn) 或者 左節(jié)點(diǎn)
        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é)點(diǎn)左右子節(jié)點(diǎn)都不為空
        else if (current.left != null && current.right != null) {
            // 找到刪除節(jié)點(diǎn)的后繼者
            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é)點(diǎn)的后繼者
     *      刪除節(jié)點(diǎn)的后繼者是在其右節(jié)點(diǎn)樹種最小的節(jié)點(diǎn)
     * @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é)點(diǎn)樹)是否有右節(jié)點(diǎn)樹
        // 如果它有右節(jié)點(diǎn)樹,則替換后繼者位置,加到后繼者父親節(jié)點(diǎn)的左節(jié)點(diǎn).
        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é)點(diǎn)
 */
class TreeNode {

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

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

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

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

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

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

面試點(diǎn)二：如何確定二叉樹的最大深度或者最小深度

答案：簡單的遞歸實現(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;
    }

面試點(diǎn)三：如何確定二叉樹是否是平衡二叉樹

答案：簡單的遞歸實現(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;
    }

前面面試點(diǎn)是二叉樹的楞艾，后面面試點(diǎn)是搜索二叉樹的。先運(yùn)行搜搜二叉樹代碼：

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é)點(diǎn)值10
        TreeNode node01 = b.search(10);
        System.out.println("是否存在節(jié)點(diǎn)值為10 => " + node01.value);
        // 是否存在節(jié)點(diǎn)值11
        TreeNode node02 = b.search(11);
        System.out.println("是否存在節(jié)點(diǎn)值為11 => " + node02);

        // 刪除節(jié)點(diǎn)8
        TreeNode node03 = b.delete(8);
        System.out.println("刪除節(jié)點(diǎn)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é)點(diǎn)值為10 => 10
是否存在節(jié)點(diǎn)值為11 => null
刪除節(jié)點(diǎn)8 => 8
value = 1 -> value = 2 -> value = 3 -> value = 4 -> value = 6 -> value = 9 -> value = 10 -> value = 20 -> value = 25 ->