一文高效图解二叉树面试题

来自:码出高效面试的程序媛(微信号:mcgx1024),作者:程序媛

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

一、树 & 二叉树

树的组成为节点和边,节点用来储存元素。节点组成为根节点、父节点和子节点。

如图:树深 length 为 4;根节点的值为 5 ;父子节点关系:值为 8 和 值为 3 的节点

理解了树,那什么是二叉树?

二叉树 (Binary Tree),二叉是分叉的意思,就是用边区分。节点最多有两个子节点,分别为左子节点和右子节点。连接节点的就是边,所以节点最多会有三条边。二叉树的场景很多,比如用来表示算术表达式等等。

如图:值为 1 或者 8 的节点是左节点;值为 2 或 3 的节点是右节点;

二、二叉搜索树 BST

上面理解了二叉树,那么搜索二叉树就好理解了。搜索二叉树为了搜索而设计,要求也是将无序存储变成有序。即每个节点的值要比左子树的值大,比右子树的值小。

如图:

Java 实现代码如下:

  1. public class BinarySearchTree {

  2.    /**

  3.     * 根节点

  4.     */

  5.    public static TreeNode root;


  6.    public BinarySearchTree() {

  7.        this.root = null;

  8.    }


  9.    /**

  10.     * 查找

  11.     */

  12.    public TreeNode search (int key) {

  13.        TreeNode current = root;

  14.        while (current != null

  15.                && key != current.value) {

  16.            if (key < current.value )

  17.                current = current.left;

  18.            else

  19.                current = current.right;

  20.        }

  21.        return current;

  22.    }


  23.    /**

  24.     * 插入

  25.     */

  26.    public TreeNode insert (int key) {

  27.        // 新增节点

  28.        TreeNode newNode = new TreeNode(key);

  29.        // 当前节点

  30.        TreeNode current = root;

  31.        // 上个节点

  32.        TreeNode parent  = null;

  33.        // 如果根节点为空

  34.        if (current == null) {

  35.            root = newNode;

  36.            return newNode;

  37.        }

  38.        while (true) {

  39.            parent = current;

  40.            if (key < current.value) {

  41.                current = current.left;

  42.                if (current == null) {

  43.                    parent.left = newNode;

  44.                    return newNode;

  45.                }

  46.            } else {

  47.                current = current.right;

  48.                if (current == null) {

  49.                    parent.right = newNode;

  50.                    return newNode;

  51.                }

  52.            }

  53.        }

  54.    }


  55.    /**

  56.     * 删除节点

  57.     */

  58.    public TreeNode delete (int key) {

  59.        TreeNode parent  = root;

  60.        TreeNode current = root;

  61.        boolean isLeftChild = false;

  62.        // 找到删除节点 及 是否在左子树

  63.        while (current.value != key) {

  64.            parent = current;

  65.            if (current.value > key) {

  66.                isLeftChild = true;

  67.                current = current.left;

  68.            } else {

  69.                isLeftChild = false;

  70.                current = current.right;

  71.            }


  72.            if (current == null) {

  73.                return current;

  74.            }

  75.        }


  76.        // 如果删除节点左节点为空 , 右节点也为空

  77.        if (current.left == null && current.right == null) {

  78.            if (current == root) {

  79.                root = null;

  80.            }

  81.            // 在左子树

  82.            if (isLeftChild == true) {

  83.                parent.left = null;

  84.            } else {

  85.                parent.right = null;

  86.            }

  87.        }

  88.        // 如果删除节点只有一个子节点 右节点 或者 左节点

  89.        else if (current.right == null) {

  90.            if (current == root) {

  91.                root = current.left;

  92.            } else if (isLeftChild) {

  93.                parent.left = current.left;

  94.            } else {

  95.                parent.right = current.left;

  96.            }


  97.        }

  98.        else if (current.left == null) {

  99.            if (current == root) {

  100.                root = current.right;

  101.            } else if (isLeftChild) {

  102.                parent.left = current.right;

  103.            } else {

  104.                parent.right = current.right;

  105.            }

  106.        }

  107.        // 如果删除节点左右子节点都不为空

  108.        else if (current.left != null && current.right != null) {

  109.            // 找到删除节点的后继者

  110.            TreeNode successor = getDeleteSuccessor(current);

  111.            if (current == root) {

  112.                root = successor;

  113.            } else if (isLeftChild) {

  114.                parent.left = successor;

  115.            } else {

  116.                parent.right = successor;

  117.            }

  118.            successor.left = current.left;

  119.        }

  120.        return current;

  121.    }


  122.    /**

  123.     * 获取删除节点的后继者

  124.     *      删除节点的后继者是在其右节点树种最小的节点

  125.     */

  126.    public TreeNode getDeleteSuccessor(TreeNode deleteNode) {

  127.        // 后继者

  128.        TreeNode successor = null;

  129.        TreeNode successorParent = null;

  130.        TreeNode current = deleteNode.right;


  131.        while (current != null) {

  132.            successorParent = successor;

  133.            successor = current;

  134.            current = current.left;

  135.        }


  136.        // 检查后继者(不可能有左节点树)是否有右节点树

  137.        // 如果它有右节点树,则替换后继者位置,加到后继者父亲节点的左节点.

  138.        if (successor != deleteNode.right) {

  139.            successorParent.left = successor.right;

  140.            successor.right = deleteNode.right;

  141.        }


  142.        return successor;

  143.    }


  144.    public void toString(TreeNode root) {

  145.        if (root != null) {

  146.            toString(root.left);

  147.            System.out.print("value = " + root.value + " -> ");

  148.            toString(root.right);

  149.        }

  150.    }

  151. }


  152. /**

  153. * 节点

  154. */

  155. class TreeNode {


  156.    /**

  157.     * 节点值

  158.     */

  159.    int value;


  160.    /**

  161.     * 左节点

  162.     */

  163.    TreeNode left;


  164.    /**

  165.     * 右节点

  166.     */

  167.    TreeNode right;


  168.    public TreeNode(int value) {

  169.        this.value = value;

  170.        left  = null;

  171.        right = null;

  172.    }

  173. }

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

节点数据结构,即节点、左节点和右节点。如图

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

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

  1. int maxDeath(TreeNode node){

  2.    if(node==null){

  3.        return 0;

  4.    }

  5.    int left = maxDeath(node.left);

  6.    int right = maxDeath(node.right);

  7.    return Math.max(left,right) + 1;

  8. }


  9.    int getMinDepth(TreeNode root){

  10.        if(root == null){

  11.            return 0;

  12.        }

  13.        return getMin(root);

  14.    }

  15.    int getMin(TreeNode root){

  16.        if(root == null){

  17.            return Integer.MAX_VALUE;

  18.        }

  19.        if(root.left == null&&root.right == null){

  20.            return 1;

  21.        }

  22.        return Math.min(getMin(root.left),getMin(root.right)) + 1;

  23.    }

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

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

一文高效图解二叉树面试题.png

前面面试点是 二叉树 的,后面面试点是 搜索二叉树 的。先运行搜搜二叉树代码:

  1. public class BinarySearchTreeTest {


  2.    public static void main(String[] args) {

  3.        BinarySearchTree b = new BinarySearchTree();

  4.        b.insert(3);b.insert(8);b.insert(1);b.insert(4);b.insert(6);

  5.        b.insert(2);b.insert(10);b.insert(9);b.insert(20);b.insert(25);


  6.        // 打印二叉树

  7.        b.toString(b.root);

  8.        System.out.println();


  9.        // 是否存在节点值10

  10.        TreeNode node01 = b.search(10);

  11.        System.out.println("是否存在节点值为10 => " + node01.value);

  12.        // 是否存在节点值11

  13.        TreeNode node02 = b.search(11);

  14.        System.out.println("是否存在节点值为11 => " + node02);


  15.        // 删除节点8

  16.        TreeNode node03 = b.delete(8);

  17.        System.out.println("删除节点8 => " + node03.value);

  18.        b.toString(b.root);



  19.    }

  20. }

结果如下:

一文高效图解二叉树面试题.png
一文高效图解二叉树面试题.png

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

插入,还是比较容易理解的。就按照要求,插入到指定的位置。如果插入到叉搜索树的中间节点,那么会引起节点的动态变化。如图插入的逻辑:

  1. 值为 2 的节点开始判断

  2. 如果为空,则插入该节点

  3. 循环下面节点:

    1. 节点当前值大于,继续循环左节点

    2. 节点当前值小于,继续循环右节点

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

算法复杂度 : O(lgN)。如图搜索及查找逻辑:

  1. 值为 2 的节点开始判断

    1. 节点当前值大于,继续循环左节点

    2. 节点当前值小于,继续循环右节点

  2. 如果值相等,搜索到对应的值,并返回

  3. 如果循环完毕没有,则返回未找到

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

比较复杂了。相比新增、搜搜,删除需要将树重置。逻辑为:删除的节点后,其替代的节点为,其右节点树中值最小对应的节点。如图:

结果为:

三、小结

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

面试必备小结:

  • 树,二叉树的概念

  • BST 算法

推荐↓↓↓
算法与数据结构
上一篇:漫画:面试官考我图形推理题,我该怎么办? 下一篇:什么是优先队列?