一文图解二叉树面试题，现在懂了吗？
一、树 & 二叉树
树是由节点和边构成，储存元素的集合。节点分根节点、父节点和子节点的概念。
如图：树深=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;
publicBinarySearchTree() {
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;
}returncurrent;
}
/** * 插入
* 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;returnnewNode;
}while(true) {
parent = current;if(key < current.value) {
current = current.left;if(current == null) {
parent.left = newNode;returnnewNode;
}
}else{
current = current.right;if(current == null) {
parent.right = newNode;returnnewNode;
}
}
}
}
/** * 删除节点
* 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);
returnMath.max(left,right) + 1;
}
int getMinDepth(TreeNode root){
if(root == null){return0;
}
return getMin(root);
}
int getMin(TreeNode root){
if(root == null){
return Integer.MAX_VALUE;
}
if(root.left == null&&root.right == null){
return1;
}
return Math.min(getMin(root.left),getMin(root.right)) + 1;
}
面试点三：如何确定二叉树是否是平衡二叉树
答案：简单的递归实现即可，代码如下：
boolean isBalanced(TreeNode node){
returnmaxDeath2(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;
}
returnMath.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 => 8value = 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
查找完毕未找到
面试点五：搜索二叉树如何实现删除
比较复杂了。首先找到删除节点，其寻找方法：删除节点的后继者是在其右节点树种最小的节点。如图删除对应逻辑：
结果为：
（1）找到删除节点
（2）如果删除节点左节点为空 , 右节点也为空
（3）如果删除节点只有一个子节点 右节点 或者 左节点
（4）如果删除节点左右子节点都不为空
三、小结
就像码出高效面试的程序媛偶尔吃一碗“老坛酸菜牛肉面”一样的味道，品味一个算法，比如 BST 的时候，总是那种说不出的味道。
