当前位置:首页 > 公众号精选 > 技术让梦想更伟大
[导读]关注、星标公众号,直达精彩内容文章来源:segmentfault作者:Ethson【导读】:树是数据结构中的重中之重,尤其以各类二叉树为学习的难点。在面试环节中,二叉树也是必考的模块。本文主要讲二叉树操作的相关知识,梳理面试常考的内容。请大家跟随小编一起来复习吧。本文针对面试中常...

文章来源:segmentfault


作者:Ethson



导读】:树是数据结构中的重中之重,尤其以各类二叉树为学习的难点。在面试环节中,二叉树也是必考的模块。本文主要讲二叉树操作的相关知识,梳理面试常考的内容。请大家跟随小编一起来复习吧。



本文针对面试中常见的二叉树操作做个总结:


  1. 前序遍历,中序遍历,后序遍历;
  2. 层次遍历;
  3. 求树的结点数;
  4. 求树的叶子数;
  5. 求树的深度;
  6. 求二叉树第k层的结点个数;
  7. 判断两棵二叉树是否结构相同;
  8. 求二叉树的镜像;
  9. 求两个结点的最低公共祖先结点;
  10. 求任意两结点距离;
  11. 找出二叉树中某个结点的所有祖先结点;
  12. 不使用递归和栈遍历二叉树;
  13. 二叉树前序中序推后序;
  14. 判断二叉树是不是完全二叉树;
  15. 判断是否是二叉查找树的后序遍历结果;
  16. 给定一个二叉查找树中的结点,找出在中序遍历下它的后继和前驱;
  17. 二分查找树转化为排序的循环双链表;
  18. 有序链表转化为平衡的二分查找树;
  19. 判断是否是二叉查找树。

1 前序遍历,中序遍历,后序遍历;

1.1 前序遍历

对于当前结点,先输出该结点,然后输出它的左孩子,最后输出它的右孩子。以上图为例,递归的过程如下:


  1. 输出 1,接着左孩子;
  2. 输出 2,接着左孩子;
  3. 输出 4,左孩子为空,再接着右孩子;
  4. 输出 6,左孩子为空,再接着右孩子;
  5. 输出 7,左右孩子都为空,此时 2 的左子树全部输出,2 的右子树为空,此时 1 的左子树全部输出,接着 1 的右子树;
  6. 输出 3,接着左孩子;
  7. 输出 5,左右孩子为空,此时 3 的左子树全部输出,3 的右子树为空,至此 1 的右子树全部输出,结束。
而非递归版本只是利用 stack 模拟上述过程而已,递归的过程也就是出入栈的过程。


/* 前序遍历递归版 */
void PreOrderRec(Node * node)
{
if (node == nullptr)
return;
cout << node->data << " ";   // 先输出当前结点
PreOrderRec(node->left);     // 然后输出左孩子
PreOrderRec(node->right);    // 最后输出右孩子
}

/* 前序遍历非递归版 */
void PreOrderNonRec(Node * node)
{
if (node == nullptr)
return;

stack S;
cout << node->data << " ";
S.push(node);
node = node->left;

while (!S.empty() || node)
{
while (node)
{
cout << node->data << " "; // 先输出当前结点
S.push(node);
node = node->left;         // 然后输出左孩子
}                              // while 结束意味着左孩子已经全部输出

node = S.top()->right;         // 最后输出右孩子
S.pop();
}
}

1.2 中序遍历

对于当前结点,先输出它的左孩子,然后输出该结点,最后输出它的右孩子。以(1.1)图为例:


  1. 1-->2-->4,4 的左孩子为空,输出 4,接着右孩子;
  2. 6 的左孩子为空,输出 6,接着右孩子;
  3. 7 的左孩子为空,输出 7,右孩子也为空,此时 2 的左子树全部输出,输出 2,2 的右孩子为空,此时 1 的左子树全部输出,输出 1,接着 1 的右孩子;
  4. 3-->5,5 左孩子为空,输出 5,右孩子也为空,此时 3 的左子树全部输出,而 3 的右孩子为空,至此 1 的右子树全部输出,结束。
/* 中序遍历递归版 */
void InOrderRec(Node * node)
{
if (node == nullptr)
return;

InOrderRec(node->left);     // 先输出左孩子
cout << node->data << " ";  // 然后输出当前结点
InOrderRec(node->right);    // 最后输出右孩子
}

/* 前序遍历非递归版 */
void InOrderNonRec(Node * node)
{
if (node == nullptr)
return;

stack S;
S.push(node);
node = node->left;

while (!S.empty() || node)
{
while (node)
{
S.push(node);
node = node->left;
}                             // while 结束意味着左孩子为空

cout << S.top()->data << " "; // 左孩子已经全部输出,接着输出当前结点
node = S.top()->right;        // 左孩子全部输出,当前结点也输出后,最后输出右孩子
S.pop();
}
}

1.3 后序遍历

对于当前结点,先输出它的左孩子,然后输出它的右孩子,最后输出该结点。依旧以(1.1)图为例:


  1. 1->2->4->6->7,7 无左孩子,也无右孩子,输出 7,此时 6 无左孩子,而 6 的右子树也全部输出,输出 6,此时 4 无左子树,而 4 的右子树已全部输出,接着输出 4,此时 2 的左子树全部输出,且 2 无右子树,输出 2,此时 1 的左子树全部输出,接着转向右子树;
  2. 3->5,5 无左孩子,也无右孩子,输出 5,此时 3 的左子树全部输出,且 3 无右孩子,输出 3,此时 1 的右子树全部输出,输出 1,结束。
非递归版本中,对于一个结点,如果我们要输出它,只有它既没有左孩子也没有右孩子或者它有孩子但是它的孩子已经被输出(由此设置 pre 变量)。若非上述两种情况,则将该结点的右孩子和左孩子依次入栈,这样就保证了每次取栈顶元素的时候,先依次遍历左子树和右子树。


/* 后序遍历递归版 */
void PostOrderRec(Node * node)
{
if (node == nullptr)
return;

PostOrderRec(node->left);   // 先输出左孩子
PostOrderRec(node->right);  // 然后输出右孩子
cout << node->data << " ";  // 最后输出当前结点
}

/* 后序遍历非递归版 */
void PostOrderNonRec(Node * node)
{
if (node == nullptr)
return;

Node * pre = nullptr;
stack S;
S.push(node);

while (!S.empty())
{
node = S.top();

if ((!node->left 
声明:本文仅代表作者本人观点,不代表本站观点,如有问题请联系站方处理。
换一批
延伸阅读

低压差 (LDO) 稳压器的本质是通过将多余的功率转化为热量来调节电压,使该集成电路成为低功率或小 V IN至 V OUT差分应用的理想解决方案。考虑到这一点,选择合适的 LDO 和合适的封装对于最大限度地提高应用程序的...

关键字: LDO 基础知识 BSP 封装

半导体设备的认证测试有许多不同类型和风格:电磁干扰和兼容性、静电放电、瞬态脉冲、抗振性、湿度和温度应力——不胜枚举。这些认证测试旨在进行真实且可重复的实验室实验,代表被测设备的应用环境。有些测试是独立的,有些是整个套件的...

关键字: 继电器 脉冲测试 KHZ BSP

在本系列的前几期中,我重点介绍了规格、传输比和基本额定功率,以及降压、升压和降压-升压拓扑。在本期中,我将介绍单端初级电感转换器 (SEPIC) 和 Zeta 转换器。在高达 25W 的功率范围内,这两种拓扑结构都可以成...

关键字: 电源设计 电流波形 SEPIC BSP

在本文系列的第二部分中,我讨论了如何从我们的电源规格参数中选择最适合的拓扑。在第三部分中,我将详细介绍降压、升压和降压-升压拓扑的不同方面。

关键字: 降压转换器 输出电压 电源设计 BSP

在这个由两部分组成的系列的第一部分中,我描述了正确设计电源的良好规范的重要性。在第 2 部分中,我将概述我们的规范中的哪些参数(参见图 1)会影响某些拓扑的决策。

关键字: 升压转换器 输出电压 电源设计 BSP

如果我们不知道如何开始以及从哪里开始设计电源,对于开关模式电源设计可能是一件神秘的事情,因为有多种拓扑结构和控制器类型可供选择。

关键字: 电感 电源设计 绕组 BSP

工厂自动化应用中的精度取决于许多因素,例如精度、温度漂移和噪声。但是,在最初设计系统时,您可能忽略了另外两个关键因素:安全性和可重复性。

关键字: 自动化 精度 浪涌电流 BSP

我们是否需要负电压来为数据转换器或放大器供电?这些类型的系统通常需要低噪声来为这种敏感的模拟电路供电。虽然经常使用线性稳压器 (LDO) 来实现低噪声,但如果开关 DC/DC 转换器本身可以提供低噪声会怎样?如果我们只能...

关键字: 降压转换器 低噪声 PS BSP

故障指示器广泛用于电网基础设施,用于监测架空和地下输电线路。这些指示器监控每相中流动的电流,并在检测到故障电流通过时向上游断路器发送命令以跳闸。

关键字: 电网 能量收集 故障指示器 BSP

洗衣机、空调和冰箱等变频家用电器通常使用无刷直流电机 (BLDC)。这些电机因其高效率、低可闻噪音和无级调速而在家用电器中很受欢迎。

关键字: 家用电器 电机驱动 BLDC BSP

编辑精选

技术子站

关闭