美文网首页Java互联网科技Java 杂谈
一文图解二叉树面试题

一文图解二叉树面试题

作者: Java_老男孩 | 来源:发表于2019-05-30 15:21 被阅读10次

    一、树 & 二叉树

    树是由节点和边构成,储存元素的集合。节点分根节点、父节点和子节点的概念。

    如图:树深=4; 5是根节点;同样8与3的关系是父子节点关系。

    二叉树binary tree,则加了“二叉”(binary),意思是在树中作区分。每个节点至多有两个子(child),left child & right child。二叉树在很多例子中使用,比如二叉树表示算术表达式。

    如图:1/8是左节点;2/3是右节点;

    二、二叉搜索树 BST

    顾名思义,二叉树上又加了个搜索的限制。其要求:每个节点比其左子树元素大,比其右子树元素小。

    如图:每个节点比它左子树的任意节点大,而且比它右子树的任意节点小

    Java 实现代码如下:

    public class BinarySearchTree {
        /**
         * 根节点
         */
        public static TreeNode root;
    
        public BinarySearchTree() {
            this.root = null;
        }
    
        /**
         * 查找
         *      树深(N) O(lgN)
         *      1\. 从root节点开始
         *      2\. 比当前节点值小,则找其左节点
         *      3\. 比当前节点值大,则找其右节点
         *      4\. 与当前节点值相等,查找到返回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节点开始
         *      2\. 如果root为空,root为插入值
         *      循环:
         *      3\. 如果当前节点值大于插入值,找左节点
         *      4\. 如果当前节点值小于插入值,找右节点
         * @param key
         * @return
         */
        public TreeNode insert (int key) {
            // 新增节点
            TreeNode newNode = new TreeNode(key);
            // 当前节点
            TreeNode current = root;
            // 上个节点
            TreeNode parent  = null;
            // 如果根节点为空
            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;
                    }
                }
            }
        }
    
        /**
         * 删除节点
         *      1.找到删除节点
         *      2.如果删除节点左节点为空 , 右节点也为空;
         *      3.如果删除节点只有一个子节点 右节点 或者 左节点
         *      4.如果删除节点左右子节点都不为空
         * @param key
         * @return
         */
        public TreeNode delete (int key) {
            TreeNode parent  = root;
            TreeNode current = root;
            boolean isLeftChild = false;
            // 找到删除节点 及 是否在左子树
            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;
                }
            }
    
            // 如果删除节点左节点为空 , 右节点也为空
            if (current.left == null && current.right == null) {
                if (current == root) {
                    root = null;
                }
                // 在左子树
                if (isLeftChild == true) {
                    parent.left = null;
                } else {
                    parent.right = null;
                }
            }
            // 如果删除节点只有一个子节点 右节点 或者 左节点
            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;
                }
            }
            // 如果删除节点左右子节点都不为空
            else if (current.left != null && current.right != null) {
                // 找到删除节点的后继者
                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;
        }
    
        /**
         * 获取删除节点的后继者
         *      删除节点的后继者是在其右节点树种最小的节点
         * @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;
            }
    
            // 检查后继者(不可能有左节点树)是否有右节点树
            // 如果它有右节点树,则替换后继者位置,加到后继者父亲节点的左节点.
            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);
            }
        }
    }
    
    /**
     * 节点
     */
    class TreeNode {
    
        /**
         * 节点值
         */
        int value;
    
        /**
         * 左节点
         */
        TreeNode left;
    
        /**
         * 右节点
         */
        TreeNode right;
    
        public TreeNode(int value) {
            this.value = value;
            left  = null;
            right = null;
        }
    }
    

    面试点一:理解 TreeNode 数据结构

    节点数据结构,即节点分左节点和右节点及本身节点值。如图

    面试点二:如何确定二叉树的最大深度或者最小深度

    答案:简单的递归实现即可,代码如下:

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

    面试点三:如何确定二叉树是否是平衡二叉树

    答案:简单的递归实现即可,代码如下:

        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();
    
            // 是否存在节点值10
            TreeNode node01 = b.search(10);
            System.out.println("是否存在节点值为10 => " + node01.value);
            // 是否存在节点值11
            TreeNode node02 = b.search(11);
            System.out.println("是否存在节点值为11 => " + node02);
    
            // 删除节点8
            TreeNode node03 = b.delete(8);
            System.out.println("删除节点8 => " + node03.value);
            b.toString(b.root);
    
        }
    }
    

    结果如下:

    value = 1 -> value = 2 -> value = 3 -> value = 4 -> value = 6 -> value = 8 -> value = 9 -> value = 10 -> value = 20 -> value = 25 -> 
    是否存在节点值为10 => 10
    是否存在节点值为11 => null
    删除节点8 => 8
    value = 1 -> value = 2 -> value = 3 -> value = 4 -> value = 6 -> value = 9 -> value = 10 -> value = 20 -> value = 25 ->
    
    

    面试点四:搜索二叉树如何实现插入

    插入,和删除一样会引起二叉搜索树的动态变化。插入相对删处理逻辑相对简单些。如图插入的逻辑:

    1. 从root节点开始
    2. 如果root为空,root为插入值
    3. 循环:
    4. 如果当前节点值大于插入值,找左节点
    5. 如果当前节点值小于插入值,找右节点

    面试点五:搜索二叉树如何实现查找

    其算法复杂度 : O(lgN),树深(N)。如图查找逻辑:

    1. 从root节点开始
    2. 比当前节点值小,则找其左节点
    3. 比当前节点值大,则找其右节点
    4. 与当前节点值相等,查找到返回TRUE
    5. 查找完毕未找到

    面试点五:搜索二叉树如何实现删除

    比较复杂了。首先找到删除节点,其寻找方法:删除节点的后继者是在其右节点树种最小的节点。如图删除对应逻辑:

    结果为:

    1. 找到删除节点
    2. 如果删除节点左节点为空 , 右节点也为空
    3. 如果删除节点只有一个子节点 右节点 或者 左节点
    4. 如果删除节点左右子节点都不为空

    三、小结

    就像码出高效面试的程序媛偶尔吃一碗“老坛酸菜牛肉面”一样的味道,品味一个算法,比如 BST 的时候,总是那种说不出的味道。

    相关文章

      网友评论

        本文标题:一文图解二叉树面试题

        本文链接:https://www.haomeiwen.com/subject/mflvtctx.html