我挂树上了：一道树的面试题

点击上方“java进阶架构师”，选择右上角“置顶公众号”

20大进阶架构专题每日送达

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

一、树 & 二叉树

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

如图：树深 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. }

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

答案：简单的递归实现即可，代码如下：

1. boolean isBalanced(TreeNode node){

2. return maxDeath2(node)!=-1;

3. }

4. int maxDeath2(TreeNode node){

5. if(node == null){

6. return 0;

7. }

8. int left = maxDeath2(node.left);

9. int right = maxDeath2(node.right);

10. if(left==-1||right==-1||Math.abs(left-right)>1){

11. return -1;

12. }

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

14. }

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

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

结果如下：

1. value = 1 -> value = 2 -> value = 3 -> value = 4 -> value = 6 -> value = 8 -> value = 9 -> value = 10 -> value = 20 -> value = 25 ->

2. 是否存在节点值为10 => 10

3. 是否存在节点值为11 => null

4. 删除节点8 => 8

5. value = 1 -> value = 2 -> value = 3 -> value = 4 -> value = 6 -> value = 9 -> value = 10 -> value = 20 -> value = 25 ->

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

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

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

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

3. 循环下面节点:

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

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

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

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

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

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

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

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

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

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

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

结果为：

三、小结

面试必备小结：

• 树，二叉树的概念

• BST 算法

————  e n d ————

快年底了，师长为大家准备了三份面试宝典：

• 《java面试宝典5.0》

• 《350道Java面试题：整理自100+公司》

• 《资深java面试宝典-视频版》

分别适用于初中级，中高级，以及资深级工程师的面试复习。

内容包含java基础、javaweb、各个性能优化、JVM、锁、高并发、反射、Spring原理、微服务、Zookeeper、数据库、数据结构、限流熔断降级等等。

获取方式：点“在看”，V信关注师长的小号：编程最前线并回复 面试 领取，更多精彩陆续奉上。

一、初中级《java面试宝典5.0》，对标8-13K

二、中高级《350道Java面试题：整理自100+公司》，对标12-20K

三、资深《java面试突击-视频版》，对标20K+

点在看好不好，喵~