前置知识:
- 二叉树的先序遍历:先遍历根节点,再遍历左儿子(若有),最后遍历右儿子(若有)。
- 二叉树的中序遍历:先遍历左儿子(若有),再遍历根节点,最后遍历右儿子(若有)。
- 二叉树的后序遍历:先遍历左儿子(若有),再遍历右儿子(若有),最后遍历根节点。
- 当二叉树的输入是先序遍历的时候,使用栈可以以非递归方式实现二叉树的中序遍历。
- 若仅知道某棵二叉树的先序遍历和后序遍历,则其中序遍历未必唯一,其中序遍历的数量是
(树中仅有一个子节点的节点数量)^ 2
,这样若存在这样的子节点,那么它可以选择在左子树也可以选择在右子树,根据乘法原理,故是2次方,通过先序遍历和后序遍历的性质可以发现,若某个节点x
仅有一个子节点y
,那么它在先序遍历中会是x y
,后序遍历中会是y x
,故可以两重循环枚举得出符合的数量- 如何判断二叉树是对称二叉树:可以对树分别跑先序遍历和后序遍历,如果先序遍历等于逆向的后序遍历则说明是对称的(由于部分儿子节点可能是空的,所以对于空的节点需要加上,加入一个虚拟值即可)。
- 对于二叉搜索树而言,它的先序遍历等于逆序的关于镜像对称的二叉搜索树的后序遍历。
- 对于二叉搜索树而言,它的中序遍历是非递减序。
- 对于完全二叉树而言,它的层序遍历等于将存储的数组直接顺序输出一遍(
1
是根,2 * 1
是左儿子,…)。- 对于完全二叉树而言,若已知它的任意遍历顺序,则都能够通过模拟该遍历顺序,构建出完全二叉树各节点的值。
- 如何判断树是否是完全二叉树:如果所给的树能够将节点信息连续的放在一维数组中,则是,反之则不是。
- 给定一组数字序列,构造一棵二叉搜索树:判断树是否为空,如果是则当前这个数作为根,否则判断当前数和根节点大小关系,若小则递归到左子树去比较,若大则递归到右子树去比较。
已知xx
遍历和中序遍历时,这个xx
遍历目的是为了确定当前子树的根节点是谁,进而将中序划分,再去找合法的根节点,这样递归下去最终建树。(一道变形题: 笛卡尔树 )
已知先序遍历和后序遍历时,求某一合法的中序遍历:与上文方式类似,函数中所传的参数是当前子树在先序和后序遍历的序列中的边界情况,其中由于根左右
、左右根
的遍历形式,可能会出现x根
、根x
,也就是不同时存在左右子树,此时可以假设不存在右子树,将x
放到左子树中去。对于有左右子树的,在划分子树区间时,要明确当先序遍历中第一次遇到右子树的根时,下标减一便是左子树的范围,后序遍历中第一次遇到左子树的根时,下标加一便是右子树的范围。
已知二叉树的后序遍历和中序遍历,构建二叉树:
思路:
1. 后序遍历的结构是左右根,也就是说根节点一定是在后序遍历的末尾处,而中序遍历是左根右,所以如果能够知道根节点的位置,可以将区间划分为左儿子和右儿子。
2. 结合各节点数值不同、需要记录两个儿子信息、需要知道根节点在中序遍历的位置,故可以用哈希表来记录信息(这里树结构本身无序,故用unordered_map
)。
3. 知道了左右儿子后,可以递归的向下继续划分,并每次返回当前子树根节点。
4. 但仅知道这些对于部分人还不够(比如我)。因为整个过程都在不断地对区间进行划分,所以需要知道以每个元素为根的子树它的后序遍历和中序遍历在原始序列的范围。这里假定当前元素为v
, 它在中序遍历中处于k
, 它的子树两种遍历范围分别是l1, r1, l2, r2
(中序遍历,后序遍历),那么当存在左右儿子时:
左儿子的中序遍历区间:
l1, k - 1
(可知道左儿子树上共有节点k - 1 - l1 + 1
),则后序遍历区间:l2, l2 + k - 1 - l1
右儿子的中序遍历区间:k + 1, r1
(可知道右儿子树上共有节点r1 - k - 1 + 1
),则后序遍历区间:r2 - r1 + k, r2 - 1
补充:其实为什么需要划分区间,因为想要知道所有子树的根节点是谁(也就是后序遍历序列的右端点),而通过中序遍历的划分能够知道左右儿子的数量,进而能够知道在原始的后序遍历中以左/右儿子为根的树的范围是哪里。
题目:树的遍历
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
const int N = 35;
int n, cnt;
int suf[N], mid[N];
unordered_map<int, int> pos; // 每个元素在中序遍历出现的位置
unordered_map<int, int> lchild, rchild;
// 该子树中序遍历所在范围,后序遍历所在范围
int build(int l1, int r1, int l2, int r2)
{
int v = suf[r2];
int k = pos[v];
if(k > l1)
lchild[v] = build(l1, k - 1, l2, l2 + k - l1 - 1);
if(k < r1)
rchild[v] = build(k + 1, r1, r2 - r1 + k, r2 - 1);
return v;
}
void bfs()
{
queue<int> q;
q.push(suf[n]);
while(q.size())
{
auto t = q.front();
cout << t << " ";
q.pop();
if(lchild.count(t)) q.push(lchild[t]);
if(rchild.count(t)) q.push(rchild[t]);
}
}
int main()
{
cin >> n;
for(int i = 1;i <= n;i ++ ) cin >> suf[i];
for(int i = 1;i <= n;i ++ )
{
cin >> mid[i];
pos[mid[i]] = i;
}
build(1, n, 1, n);
bfs();
return 0;
}
已知二叉树的先序遍历和中序遍历,构建二叉树:
思路与前文类似,但在划分区间时要注意先序遍历的根是在最左边。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
const int N = 50010;
int n;
unordered_map<int, int> pos, l, r;
int pre[N], mid[N];
vector<int> suf;
int build(int il, int ir, int pl, int pr)
{
int v = pre[pl];
int k = pos[v];
if(k > il)
l[v] = build(il, k - 1, pl + 1, pl + k - il);
if(k < ir)
r[v] = build(k + 1, ir, pl + k - il + 1, pr);
return v;
}
void dfs(int u)
{
if(l.count(u)) dfs(l[u]);
if(r.count(u)) dfs(r[u]);
suf.push_back(u);
}
int main()
{
cin >> n;
for(int i = 1;i <= n;i ++ ) cin >> pre[i];
for(int i = 1;i <= n;i ++ )
{
cin >> mid[i];
pos[mid[i]] = i;
}
build(1, n, 1, n);
dfs(pre[1]);
cout << suf[0] << endl;
return 0;
}
已知先序遍历和后序遍历,求合法的中序遍历(能够计算出所有可能合法的中序遍历数量)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
const int N = 40;
int n;
int pre[N], suf[N];
unordered_map<int, int> l, r;
int cnt;
vector<int> ans;
int build(int pl, int pr, int sl, int sr)
{
int v = pre[pl];
if(pl == pr) return v;
if(pre[pl + 1] == suf[sr - 1])
{
l[v] = build(pl + 1, pr, sl, sr - 1);
cnt ++ ;
}
else
{
// 左子树的右边界,右子树的左边界
int left_right = 0, right_left = 0;
for(left_right = pl + 1;left_right <= pr;left_right ++ )
if(pre[left_right] == suf[sr - 1])
break;
for(right_left = sr - 1;right_left >= sl;right_left -- )
if(suf[right_left] == pre[pl + 1])
break;
left_right -- , right_left ++ ;
l[v] = build(pl + 1, left_right, sl, right_left - 1);
r[v] = build(left_right + 1, pr, right_left, sr - 1);
}
return v;
}
void dfs(int u)
{
if(l.count(u)) dfs(l[u]);
ans.push_back(u);
if(r.count(u)) dfs(r[u]);
}
int main()
{
cin >> n;
for(int i = 1;i <= n;i ++ )
cin >> pre[i];
for(int i = 1;i <= n;i ++ )
cin >> suf[i];
int root = build(1, n, 1, n);
if(cnt == 0) puts("Yes");
else puts("No");
dfs(root);
for(int i = 0;i < n;i ++ )
if(!i) cout << ans[i];
else cout << " " << ans[i];
cout << endl;
return 0;
}