题目 结点的度 先序遍历 中序遍历 后序遍历 求先序遍历
结点的度
题目大意
给定一棵以 111 为根的树，共 nnn 个结点，树用 n−1n-1n−1 条边表示父子关系。你需要处理 qqq 个查询，每次询问一个结点的度数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 树是有向关系：输入中给定的是 fafafa 是 sonsonson 的父亲；
* 但我们要输出的是度数，即该结点连接的边数（子结点数量）；
* 因为输入的是有向边（从父到子），所以只需统计每个点作为父节点出现的次数即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
一、数组记录度数
* 用数组 deg[i]deg[i]deg[i] 表示第 iii 个结点的度；
* 每读入一对边 (fa,son)(fa, son)(fa,son)，令 deg[fa]++deg[fa]++deg[fa]++；
* 每个子节点 sonsonson 不需要处理（因为题目不问入度）；
* 对每个查询 xxx，输出 deg[x]deg[x]deg[x] 即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 建树处理 n−1n-1n−1 条边，时间 O(n)O(n)O(n)；
* 查询 qqq 次，每次 O(1)O(1)O(1)；
* 总体时间复杂度：O(n+q)\boxed{O(n + q)}O(n+q) ；
* 空间复杂度：O(n)O(n)O(n)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
先序遍历
题目大意
给定一个长度为 nnn 的数组，将其构造成完全二叉树的结构（根结点编号为 111，左儿子为 2x2x2x，右儿子为 2x+12x+12x+1），然后输出整棵二叉树的先序遍历结果。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
我们可以把数组想象成完全二叉树的顺序存储结构：
* 树的根是数组下标 111；
* 每个结点编号 xxx：
* 左儿子编号为 2x2x2x；
* 右儿子编号为 2x+12x+12x+1；
* 当 x>nx > nx>n 时视为越界（无该结点）；
* 遍历顺序为：
先序遍历=根→左子树→右子树\text{先序遍历} = \text{根} \rightarrow \text{左子树} \rightarrow \text{右子树}先序遍历=根→左子树→右子树
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
* 用数组 a[1∼n]a[1\sim n]a[1∼n] 储存树的顺序结构；
* 定义一个递归函数 dfs(x)：
* 若 x>nx > nx>n：越界，返回；
* 否则：
* 输出当前结点 a[x]；
* 递归访问左儿子 dfs(2x)；
* 递归访问右儿子 dfs(2x + 1)；
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 树中最多访问每个结点一次；
* 总时间复杂度为 O(n)\boxed{O(n)}O(n) 。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现
中序遍历
题目大意
给定一个长度为 nnn 的数组，将其构造成完全二叉树的结构（根结点编号为 111，左儿子为 2x2x2x，右儿子为 2x+12x+12x+1），然后输出整棵二叉树的中序遍历结果。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
我们可以把数组想象成完全二叉树的顺序存储结构：
* 树的根是数组下标 111；
* 每个结点编号 xxx：
* 左儿子编号为 2x2x2x；
* 右儿子编号为 2x+12x+12x+1；
* 当 x>nx > nx>n 时视为越界（无该结点）；
* 遍历顺序为：
先序遍历=左子树→根→右子树\text{先序遍历} = \text{左子树} \rightarrow \text{根} \rightarrow \text{右子树}先序遍历=左子树→根→右子树
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
* 用数组 a[1∼n]a[1\sim n]a[1∼n] 储存树的顺序结构；
* 定义一个递归函数 dfs(x)：
* 若 x>nx > nx>n：越界，返回；
* 否则：
* 递归访问左儿子 dfs(2x)；
* 输出当前结点 a[x]；
* 递归访问右儿子 dfs(2x + 1)；
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 每个结点被访问一次；
* 总时间复杂度为 O(n)\boxed{O(n)}O(n) ；
* 空间复杂度为递归栈深度，最坏为 O(n)O(n)O(n)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现
后序遍历
题目大意
给定一个长度为 nnn 的数组，将其构造成完全二叉树的结构（根结点编号为 111，左儿子为 2x2x2x，右儿子为 2x+12x+12x+1），然后输出整棵二叉树的后序遍历结果。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
我们可以把数组想象成完全二叉树的顺序存储结构：
* 树的根是数组下标 111；
* 每个结点编号 xxx：
* 左儿子编号为 2x2x2x；
* 右儿子编号为 2x+12x+12x+1；
* 当 x>nx > nx>n 时视为越界（无该结点）；
* 遍历顺序为：
先序遍历=左子树→右子树→根\text{先序遍历} = \text{左子树} \rightarrow \text{右子树} \rightarrow \text{根}先序遍历=左子树→右子树→根
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
* 用数组 a[1∼n]a[1\sim n]a[1∼n] 储存树的顺序结构；
* 定义一个递归函数 dfs(x)：
* 若 x>nx > nx>n：越界，返回；
* 否则：
* 递归访问左儿子 dfs(2x)；
* 递归访问右儿子 dfs(2x + 1)；
* 输出当前结点 a[x]；
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 每个结点被访问一次；
* 总时间复杂度为 O(n)\boxed{O(n)}O(n) ；
* 空间复杂度为递归栈深度，最坏为 O(n)O(n)O(n)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
求先序遍历
题目大意
给定一棵二叉树的：
* 中序遍历字符串
* 后序遍历字符串
请根据这两种遍历结果，重建这棵二叉树的结构，并输出它的 先序遍历。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
我们利用中序和后序遍历的性质：
* 后序遍历： 最后一个节点是当前子树的 根节点
* 中序遍历： 根节点左边是 左子树，右边是 右子树
通过递归不断划分左子树和右子树，就可以重建整个先序遍历。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
函数定义
设函数 func(s, t)：
* 参数 sss 为当前子树的 中序遍历字符串
* 参数 ttt 为当前子树的 后序遍历字符串
* 根节点是 ttt 的最后一个字符
步骤如下：
1. 找根节点：root=t.back()root = t.back()root=t.back()
2. 在中序中定位根的位置：分出左子树、右子树
3. 递归处理左子树：
* 中序：s[0,id−1]s[0, id-1]s[0,id−1]
* 后序：t[0,id−1]t[0, id-1]t[0,id−1]
4. 递归处理右子树：
* 中序：s[id+1,end]s[id+1, end]s[id+1,end]
* 后序：t[id,end−1]t[id, end-1]t[id,end−1]
5. 先输出根，再递归左右子树（先序遍历顺序：根-左-右）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 每个结点最多处理一次；
* 每次字符串分割代价为 O(n)O(n)O(n)，但总的深度不超过 nnn 层；
* 总体时间复杂度 O(n2)\boxed{O(n^2)}O(n2) ，对于 n≤8n \leq 8n≤8 足够。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现
