最常见的二叉树面试问题和答案 [针对新手和有经验者]

介绍

数据结构是面向对象编程中最基本的概念之一。 简单地说，数据结构是一种在计算机中组织数据的特殊方式，以便对其进行有效处理。 有几种数据结构，如堆栈、队列和树，它们都有自己独特的属性。

树允许我们以分层方式组织数据。 这种数据结构与链表或数组等线性数据结构非常不同。 树由携带信息的节点组成。

二叉树是一种特殊类型的树，最多只能有两个孩子。 这意味着二叉树中的特定节点可以没有孩子、一个孩子或两个孩子，但不能有更多。 二叉树是一种重要的数据结构，可以帮助我们解决难题并构建复杂的代码。

如果你申请的是 Java 开发人员或软件工程师的工作，你的面试可能会包含几个围绕这个概念的问题。 通常，候选人发现很难回答基于二叉树、二叉搜索树和相关程序的问题。 在本文中，我们将探讨一些与二叉树相关的最常见的面试问题。 本文将帮助您更好地理解这个概念并为您做好准备，以便您找到梦想的工作！

顶级二叉树面试问答

以下部分包含基于二叉树概念的问题目录及其预期答案。

1）什么是叶节点？

二叉树或没有任何子节点的树中的任何节点都称为叶节点。

2) 什么是根节点？

树中的第一个节点或顶部节点称为根节点。

3) 如何在 Java 中找到二叉树的最低共同祖先 (LCA)？

让我们考虑作为二叉树一部分的两个节点 n1 和 n2。

n1 和 n2 的最低共同祖先 (LCA) 是距根最远的 n1 和 n2 的共享祖先。

您可以按照以下方法查找 LCA。

1. a) 找到从根节点到 n1 的路径并将其存储在一个数组中。
2. b) 找到从根节点到 n2 的路径并将其存储在一个数组中。
3. c) 遍历两条路径，直到两个数组中的值相同。

4）如何检查给定的二叉树是否是另一棵二叉树的子树？

假设我们有一棵二叉树 T。我们现在要检查二叉树 S 是否是 T 的子树。

为此，首先，尝试检查是否在 T 中找到了也在 S 中的节点。

找到这个公共节点后，检查以下节点是否也是 S 的一部分。

如果是，我们可以有把握地说 S 是 T 的子树。

必读：数据结构项目的想法和主题

5）如何找到二叉树中两个节点之间的距离？

考虑作为二叉树一部分的两个节点 n1 和 n2。

n1 和 n2 之间的距离等于从一个节点到另一个节点需要遍历的最小边数。

请务必注意，您遍历节点之间的最短距离。

6）什么是二叉搜索树？

二叉搜索树 (BST) 是一种特殊类型的二叉树，其中每个内部节点都包含一个键。 对于二叉搜索树，规则是：

1. a) 一个节点可以有一个大于该节点左子树中所有键的键。
2. b) 一个节点可以有一个小于该节点右子树中所有键的键。

因此，如果 n1 是一个键为 8 的节点，那么 n1 的左子树中的每个节点都将包含小于 8 的键，并且 n1 的右子树中的每个节点都将包含大于 8 的键。

7) 什么是自平衡树？

当发生插入和删除等操作时，自平衡二叉搜索树会自动保持其高度尽可能小。

要使 BST 自平衡，重要的是它始终遵循 BST 的规则，以便左子树具有低值键，而右子树具有高值键。

这是通过两个操作完成的：

- 左旋转

– 右旋转

8) 什么是 AVL 树？

AVL 树以其发明者的名字命名：Adelson、Velski 和 Landis。 AVL 树是一种自平衡二叉树，它检查其左子树和右子树的高度，并确保差不大于 1。这种差称为平衡因子

因此，BalanceFactor = 高度（左子树）-高度（右子树）

如果平衡因子大于 1，则使用以下一些技术平衡树：

- 左旋转

– 右旋转

- 左右旋转

– 左右旋转

另请阅读：数据结构中的排序

9) 如何在 Java 中将二叉树转换为二叉搜索树？

二叉树和二叉搜索树之间的主要区别在于，BST 遵循左子树应该具有较低的键值，而右子树应该具有较高的键值规则。 这可以使用一系列遍历技术来完成，如下所示：

1. 创建一个临时数组，存储树的中序遍历
2. 对临时数组进行排序。 您可以在此处使用任何排序算法。
3. 再次对树执行中序遍历。
4. 将数组元素一一复制到每个树节点。

10) 如何从 Java 中的二叉搜索树中删除一个节点？

BST 的删除操作可能很棘手，因为它的属性需要在操作后保留。 以下是所有三种可能的情况：

1. 要删除的节点是叶子节点。
   只需删除节点。
2. 要删除的节点有一个孩子。

在这种情况下，将子节点复制到节点并删除子节点。

1. 要删除的节点有两个孩子。

在这种情况下，找到节点的中序后继。 然后，您可以将其内容复制到节点并删除中序后继。

11) 什么是红黑树数据结构？

红黑树是一种特殊类型的自平衡树，具有以下特性：

1. 每个节点都有红色或黑色的颜色。
2. 根总是黑色的。
3. 红色节点不能有红色父节点或红色子节点。
4. 从根节点到 NULL 节点的每条路径都有相同数量的黑色节点。

必读：数据结构项目的想法和主题

12) 你如何判断两棵树是否相同？

如果两个二叉树具有相同的数据和排列，则它们是相同的。 这可以通过遍历两棵树并比较它们的数据和排列来完成。

这是可以使我们做到这一点的算法：

1. 检查根节点的数据（tree1 data ==tree2 data）
2. 递归检查左子树。 调用sameTree（tree1->左子树，tree2->左子树）
3. 同样，检查右子树
4. 如果 a,b,c 为真，则返回 1

结帐：二叉树的类型

最后的想法

在本文中，我们探讨了一些最常见的二叉搜索树面试问题。 探索更多关于数据结构的知识可以帮助你更好地掌握逻辑和编程。 您可以尝试查看本文中提到的示例，并通过更改值来构建您的基础来练习。 通过一些练习，您将能够很好地完成面试。

如果您想了解数据科学，请查看 IIIT-B 和 upGrad 的数据科学执行 PG 计划，该计划是为在职专业人士创建的，提供 10 多个案例研究和项目、实用的实践研讨会、行业专家的指导、1与行业导师一对一，400 多个小时的学习和顶级公司的工作协助。