内容简介:二叉树,搜索二叉树,是算法面试的必面题。聊聊面试点:树是由节点和边构成,储存元素的集合。节点分根节点、父节点和子节点的概念。
号外:为读者持续整理了几份最新教程,覆盖了 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 ->
面试点四:搜索二叉树如何实现插入
插入,和删除一样会引起二叉搜索树的动态变化。插入相对删处理逻辑相对简单些。如图插入的逻辑:
- 从root节点开始
- 如果root为空,root为插入值
- 循环:
- 如果当前节点值大于插入值,找左节点
- 如果当前节点值小于插入值,找右节点
面试点五:搜索二叉树如何实现查找
其算法复杂度 : O(lgN),树深(N)。如图查找逻辑:
- 从root节点开始
- 比当前节点值小,则找其左节点
- 比当前节点值大,则找其右节点
- 与当前节点值相等,查找到返回TRUE
- 查找完毕未找到
面试点五:搜索二叉树如何实现删除
比较复杂了。首先找到删除节点,其寻找方法:删除节点的后继者是在其右节点树种最小的节点。如图删除对应逻辑:
结果为:
- 找到删除节点
- 如果删除节点左节点为空 , 右节点也为空
- 如果删除节点只有一个子节点 右节点 或者 左节点
- 如果删除节点左右子节点都不为空
三、小结
就像码出高效面试的程序媛偶尔吃一碗“老坛酸菜牛肉面”一样的味道,品味一个算法,比如 BST 的时候,总是那种说不出的味道。
面试必备小结:
- 树,二叉树的概念
- BST 算法
(关注微信公众号,领取 Java 精选干货学习资料) (添加我微信:bysocket01。加入纯技术交流群,成长技术)
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 一文图解二叉树面试题
- 图解Spring循环依赖,看过之后再也不怕面试被问到了!
- 硬不硬你说了算!近 40 张图解被问千百遍的 TCP 三次握手和四次挥手面试题
- 图解集合 3 : CopyOnWriteArrayList
- 图解集合 4 :HashMap
- 图解集合 2 :LinkedList
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
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 加密工具
RGB HSV 转换
RGB HSV 互转工具