二叉树序列化题解
题意理解：层序遍历，就是从上往下，从左往右，遇到数字输出数字，空节点输出# 应该没人不理解
先序遍历：就是根左右，空的用# 代替，有人可能疑惑6 后面为啥3个 # 原因是，6 有两个空树，另外一个# 代表 4 的右子树
解题思路：
1.根据层序遍历，创建二叉树。
毫无疑问，第一个节点必定是根节点，层序遍历采用队列的思想，
1.1 ： 先把跟节点入队，
当队列不空
1.2 取出队头节点，这个节点作为二叉树的待建立的树节点。这个说法怎么理解看你的悟性了，称此节点为 R
1.3 从 层序遍历 中拿到一个字符串，可以断定这就是R 的左子树的值，（理解这部，你可以按照堆的思想理解，或者在草稿纸上画一下。）
如果这个字符串不是 # 那么将它作为节点入队。
如果是# 就把它忽略掉。
不管是不是 # 那么最终 都要把它作为 R 的左节点插入到 R 的左树中
插完后，再继续从层序遍历中取出下一个节点 （可以断定这就是R 的 右子树的值 ）
如果这个字符串不是 # 那么将它作为节点入队。
如果是# 就把它忽略掉。
不管是不是 # 那么最终 都要把它作为 R 的右节点插入到 R 的右树中 2. 先序遍历输出 二叉树，
2.1 递归输出
递归出口：遇到空树 输出# 返回
先输出当前节点，然后递归左边，再递归右边。
2.2 用栈 就可以不递归输出
把根节点入栈，
每次弹出栈顶元素，
如果有数值，输出，并且将左右子树的根节点入栈。
如果没有数值，输出 # 进入下一次循环。
具体做法：
struct node
{
int l, r;
string val;
}; 代表输的一个节点，用数组模拟二叉树 val 代表 数值， l 和 r 代表左右子树的下标，下表如果是 0 代表空树，这一部分应该大家都有基础，不再赘述，如有不懂欢迎留言。
{
int l, r;
string val;
}; 代表输的一个节点，用数组模拟二叉树 val 代表 数值， l 和 r 代表左右子树的下标，下表如果是 0 代表空树，这一部分应该大家都有基础，不再赘述，如有不懂欢迎留言。
遇到的坑： 就写在代码注释里面把
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
const int N = 1e5 + 10;
int root = 1, idx = 1;
struct node
{
int l, r;
string val;
};
node tr[N];
queue< node* > q;
string tree[N];
stack<node*> st;
void addnode(node* root, string val, int opt)
{
//着重解释 opt 的含义 如果是 1 代表将她插入到 root 的左树中，2 代表插入到右树中
int u = ++idx;
if (opt == 1)
{
root->l = u;
}
else
{
root->r = u;
}
tr[u].l = tr[u].r = 0; //作为一个新的节点 左右两树应该置位空
tr[u].val = val;
}
void output()
{
st.push(&tr[1]);
while (st.size())
{
node* t = st.top();
st.pop();
if (t->val.size() == 0) cout << "#" << endl;
else
{
cout << t->val << endl;
st.push(&tr[t->r]);
st.push(&tr[t->l]);
}
}
}
int main()
{
int n;
cin >> n;
string s;
cin >> s;
tr[root].l = tr[root].r = 0;
tr[root].val = s;
q.push(&tr[root]);
for (int i = 2; i <= n; i++) cin >> tree[i]; //规定 1是根节点，所以从2 开始
int cur = 2;
while (q.size()) //如果写成 while(true) 会发生段错误
{
node* t = q.front();
q.pop();
string l = tree[cur++];
if (l != "#")
{
addnode(t, l, 1);
q.push(&tr[t->l]);
}
if (cur > n) break; //坑 ：注意如果 这个下标已经超过 n 那么已经说明所有节点遍历完了，不要继续了
string r = tree[cur++];
if (r != "#")
{
addnode(t, r, 2);
q.push(&tr[t->r]);
}
if (cur > n) break;
}
output();
return 0;
}