2020-08-06 14:15 武汉大学 后端
关注
本题又是对二叉树这种数据结构的考察，题目的核心是要通过二叉树的前序遍历和中序遍历结果还原二叉树。
这要求我们对二叉树的遍历有着深刻的理解，这两种遍历方式特点如下：
- 前序遍历：根-左-右；先输入二叉树根结点的值，然后前序遍历左子树，再前序遍历右子树；
- 中序遍历：左-根-右；先中序遍历左子树，然后输出根节点的值，再中序遍历右子树；
将题目中的例子拿到这里来，根据前序遍历（根-左-右）的结果{1,2,4,7,3,5,6,8}，我们可以知道二叉树的根节点是1。再回到中序遍历中，我们可以看出，以1为分界线：
- 中序遍历中，左边{4,7,2}是左子树的中序遍历，右边{5,3,8,6}是右子树的中序遍历；
- 前序遍历中，{2,4,7}是左子树的前序遍历，{3,5,6,8}是右子树的前序遍历。
在前面的二叉树算法中，我们记得递归是二叉树算法中不可忽略的一部分，这道题也不例外。那么在算法中，我们只要找到root所在的位置，构造出左右子树的前序和中序遍历数组，然后递归构造而擦函数即可。
😄
这要求我们对二叉树的遍历有着深刻的理解，这两种遍历方式特点如下：
- 前序遍历：根-左-右；先输入二叉树根结点的值，然后前序遍历左子树，再前序遍历右子树；
- 中序遍历：左-根-右；先中序遍历左子树，然后输出根节点的值，再中序遍历右子树；
将题目中的例子拿到这里来，根据前序遍历（根-左-右）的结果{1,2,4,7,3,5,6,8}，我们可以知道二叉树的根节点是1。再回到中序遍历中，我们可以看出，以1为分界线：
- 中序遍历中，左边{4,7,2}是左子树的中序遍历，右边{5,3,8,6}是右子树的中序遍历；
- 前序遍历中，{2,4,7}是左子树的前序遍历，{3,5,6,8}是右子树的前序遍历。
在前面的二叉树算法中，我们记得递归是二叉树算法中不可忽略的一部分，这道题也不例外。那么在算法中，我们只要找到root所在的位置，构造出左右子树的前序和中序遍历数组，然后递归构造而擦函数即可。
😄
2020-08-06
在牛客打卡9天，今天学习：刷题 1 道/代码提交 1 次
全部评论
相关推荐
查看3道真题和解析 
投递华为等公司10个岗位 > 点赞 评论 收藏
分享