l2-011 玩转二叉树 (25 分)

### 回答1：
题目描述

本题要求给定二叉树的4种遍历结果，给出该树的结构。

输入格式:
输入给出4行，每行先给出正整数N (≤30)，随后是由空格分隔的N个整数。其中第1行给出先序遍历结果，第2行给出中序遍历结果，第3行给出后序遍历结果，第4行给出层序遍历结果。数字间以1个空格分隔，行末不得有多余空格。

输出格式:
如果输入的4种遍历结果不合法，则在一行中输出"No"，并结束程序。

如果输入的4种遍历结果合法，则在一行中输出该树的根结点的编号。如果结果不唯一，则输出其中最小的编号。

输入样例1:
7 2 3 1 5 6 7 4
2 1 3 7 5 6 4
2 7 6 5 4 3 1
1 2 4 3 5 7 6
输出样例1:
1

输入样例2:
7 2 3 1 5 6 7 4
2 3 1 7 5 6 4
2 7 6 5 4 3 1
1 2 4 3 5 7 6
输出样例2:
No

题目分析

根据二叉树的遍历序列可以构造出一棵二叉树，而给出的是四种遍历方式，因此可以将四种遍历结果输入，构造出一棵二叉树，然后在二叉树中找出根结点即可。

二叉树的构造可以使用递归函数实现，由于需要用到中序遍历，因此可以先根据中序遍历结果找到根结点，然后递归地处理左右子树。找到根结点后，可以利用先序遍历和后序遍历的性质，分别处理左右子树，得到左右子树的根结点。

时间复杂度
本题需要对四种遍历结果进行遍历，时间复杂度为 O(n)，其中 n 是二叉树的结点数。

### 回答2：
l2-011 玩转二叉树是一道二叉树的题目，需要我们熟练掌握二叉树的基本概念和常用操作，才能够解决问题。对于这道题目，主要是考察二叉树的遍历方式和二叉树的特性。

首先，我们需要了解二叉树的遍历方式。二叉树的遍历方式有前序遍历、中序遍历和后序遍历三种。其中前序遍历是指先输出根节点，再输出左子树，最后输出右子树。中序遍历是指先输出左子树，再输出根节点，最后输出右子树。后序遍历是指先输出左子树，再输出右子树，最后输出根节点。同时，还有层次遍历，它是按照从上到下，从左到右的顺序进行遍历。在解决这道题目时，需要使用到前序遍历和后序遍历。

其次，我们需要了解二叉树的特性。二叉树是一种树形结构，每个节点最多有两个孩子节点。在解决这道题目时，需要用到的是先序遍历和后序遍历，以及二叉树的性质之一：对于一个节点，它的左子树中的所有节点小于它的值，它的右子树中的所有节点大于它的值。

通过以上的了解，我们就可以开始解决这道题目。首先，我们需要输入先序遍历和后序遍历，根据先序遍历和后序遍历的特性，可以得出根节点以及它的左子树和右子树。接下来，我们需要递归的进行操作，根据左子树和右子树的特性，确定每个子树的根节点和它的左右子树。最后，就可以得到一棵完整的二叉树。

总之，这道题目主要考察对于二叉树的掌握程度，需要熟练掌握二叉树的遍历方式和特性。同时，需要学会运用递归思想，将大问题拆分成小问题，分步骤解决问题。

### 回答3：
题目描述

本题要求对给定的二叉树建立线索，并对指定结点进行遍历操作。

解题思路

本题思路较多，但有一个很关键的点，就是如何建立线索。以下简述建立线索的思路：

- 对于有左儿子的节点，将其右空指针指向其后继节点，即中序遍历下的后继节点；
- 对于有右儿子的节点，将其左空指针指向其前驱节点，即中序遍历下的前驱节点；
- 对于没有左右儿子的节点，不做任何处理。

在线索化后，就可以使用线索树进行中序遍历，省去了递归的空间开销。具体中序遍历思路如下：

- 对根节点进行转向，即将其左空指针指向前驱节点，将其右空指针指向后继节点；
- 对于每个节点，如果其左指针为空，就输出该节点并继续遍历其右孩子；否则继续转向到其左孩子节点继续遍历。

解题步骤

1.读入节点数和根节点编号，建立空的二叉树。

2.读入节点数据和父节点编号，建立二叉树。

3.进行二叉树线索化，建立线索树，省去递归空间开销。

4.根据输入要求，使用线索化的中序遍历进行操作。

5.遍历完毕，程序结束。

代码实现

本题要求使用++data存储节点数据，而不是输入的编号，所以读入节点前需要将其编号存储在map中，建立编号和数据的映射。以下是AC代码，加了少量注释以方便理解。