一文图解二叉树面试题

栏目: 数据库 · 发布时间: 5年前

内容简介:二叉树,搜索二叉树,是算法面试的必面题。聊聊面试点:树是由节点和边构成,储存元素的集合。节点分根节点、父节点和子节点的概念。

号外:为读者持续整理了几份最新教程,覆盖了 Spring Boot、Spring Cloud、微服务架构等PDF。

获取方式:关注右侧公众号"泥瓦匠BYSocket",来领取吧!

摘要: 原创出处 https://www.bysocket.com 「公众号:泥瓦匠BYSocket 」欢迎关注和转载,保留摘要,谢谢!

二叉树,搜索二叉树,是算法面试的必面题。聊聊面试点:

一、树 & 二叉树

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

如图:树深=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 的时候,总是那种说不出的味道。

面试必备小结:

  • 树,二叉树的概念
  • BST 算法

一文图解二叉树面试题 (关注微信公众号,领取 Java 精选干货学习资料) (添加我微信:bysocket01。加入纯技术交流群,成长技术)


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

CLR via C#

CLR via C#

Jeffrey Richter / 周靖 / 清华大学出版社 / 2015-1-1 / CNY 109.00

《CLR via C#(第4版)》针对CLR和.NET Framework 4.5进行深入、全面的探讨,并结合实例介绍了如何利用它们进行设计、开发和调试。全书5部分共29章。第Ⅰ部分介绍CLR基础,第Ⅱ部分解释如何设计类型,第Ⅲ部分介绍基本类型,第Ⅳ部分以核心机制为主题,第Ⅴ部分重点介绍线程处理。 通过本书的阅读,读者可以掌握CLR和.NET Framework的精髓,轻松、高效地创建高性能......一起来看看 《CLR via C#》 这本书的介绍吧!

MD5 加密
MD5 加密

MD5 加密工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具