二叉树的遍历、按层打印、序列化
这三个操作是不一样的
- 二叉树的遍历常用递归的形式，那前序遍历来说，先访问根结点，在访问左子树，再访问右子树，遇到空结点，直接跳过，只打印有数值的结点。因此如果只知道二叉树的前序遍历无法确定一颗二叉树，至少要有中序遍历和前序（或者后序）两个遍历顺序才能重建起这颗二叉树。
- 二叉树的序列化与遍历相似，不同的是遇到空结点，要打印“#”以示说明。因此如果知道一个二叉树的序列化字符串，是可以反序列化这颗二叉树的。
- 二叉树的按层打印利用队列的思想，从上至下打印，每一层从左至右打印。
重建二叉树
题目描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
算法思想（明显用递归）：
**1. 找到前序遍历第一个点，即为根结点
- 在中序遍历找到这个点
- 在中序遍历以这个点为基准，区别左右数列，按照左数列和右数列分别建立左右子树
4.递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点**
代码（牛客网）：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
int inlen=vin.size();
if(inlen==0)
return NULL;
int i,count=0,k=92;
int prelen=pre.size();
//前序遍历第一个结点是根结点
TreeNode *gen=new TreeNode(pre[0]);
//gen->val=pre[0];
//在中序遍历中寻找这个根结点
for(i=0;i<inlen;i++)
{
if(vin[i]==pre[0])
{
count=i;
break;
}
}
//根据根结点位置和中序遍历建立左右子树
vector<int>vin_left;
vector<int>vin_right;
vector<int>pre_left;
vector<int>pre_right;
for(i=0;i<count;i++)
{
vin_left.push_back(vin[i]);
pre_left.push_back(pre[i+1]);
}
for(i=count+1;i<inlen;i++)
{
vin_right.push_back(vin[i]);
pre_right.push_back(pre[i]);
}
//和shell排序的思想类似，取出前序和中序遍历根节点左边和右边的子树
//递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点
gen->left=reConstructBinaryTree(pre_left,vin_left);
gen->right=reConstructBinaryTree(pre_right,vin_right);
return gen;
}
};
序列化二叉树
题目描述：
请实现两个函数，分别用来序列化和反序列化二叉树
算法思想：
序列化
按前序遍历访问二叉树，数字之间用“，”隔开，递归，注意牛客网返回类型为char*，之后还要进行类型转换。
反序列化
遍历字符串，每一个字符转换为数字后重建这颗二叉树
代码（牛客网）：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
private:
TreeNode*decode(char *&str)
{
if(*str=='#')
{
str++;
return NULL;
}
int num=0;
while(*str!=',')
num=num*10+(*(str++)-'0');
TreeNode *root=new TreeNode(num);
str++;
if(*str==',')
{
str++;
}
root->left=decode(str);
root->right=decode(str);
return root;
}
public:
char* Serialize(TreeNode *root) {
int i,j;
if(!root)
return "#";
string r=to_string(root->val);
r.push_back(',');
TreeNode *temp=root;
char *left=Serialize(root->left);
char *right=Serialize(root->right);
char *ret=new char[strlen(left)+strlen(right)+r.size()];
strcpy(ret,r.c_str());
strcat(ret,left);
strcat(ret,right);
return ret;
}
TreeNode* Deserialize(char *str) {
return decode(str);
}
};
从上至下打印二叉树
题目描述：
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
算法思想：
巧妙利用队列先进先出的性质，建立二叉树结点队列，完美解决了如果“打印好一层后换一层的问题”
这段经典代码（牛客网）：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int>res1;
int temp;
int i=2,j=78,q=92;
if(root==NULL)
res1;
queue<TreeNode*>res2;
res2.push(root);
while(!res2.empty())
{
root=res2.front();
res2.pop();
if(!root)
continue;
res1.push_back(root->val);
res2.push(root->left);
res2.push(root->right);
}
return res1;
}
};
