LeetCode297-二叉树的序列化与反序列化:输入一棵二叉树的根节点 root
,要求你实现一个类,用serialize方法将二叉树序列化成字符串,用deserialize方法将序列化的字符串反序列化成二叉树
前序遍历
前序遍历伪代码:
void prevorderTraverse(TreeNode* root) { if (root == NULL) return; // 前序遍历代码 prevorderTraverse(root->left);//递归左子树 prevorderTraverse(root->right);//递归右子树 }
class Codec { public: int index=0; //序列化 string serialize(TreeNode* root) { string str; PreOrderTraverse(root,str);//前序遍历 return str; } //前序遍历 //将二叉树序列化为字符串,val之间用,隔开 //空节点用#表示 void PreOrderTraverse(TreeNode* root,string& str) { if(!root) { str+="#,"; return; } str=str+to_string(root->val)+",";//整型转换为字符串 PreOrderTraverse(root->left,str);//遍历左子树 PreOrderTraverse(root->right,str);//遍历右子树 } //反序列化 TreeNode* deserialize(string str) { vector<string> vec; split(str,vec);//按,进行字符串切分 return createTree(vec);//创建二叉树 } //根据前序遍历结果创建一棵二叉树 TreeNode* createTree(vector<string> vec) { if(index==vec.size()) return NULL; TreeNode* root=NULL; string str=vec[index++]; if (str != "#") { int val=atoi(str.c_str());//字符串转为整型 root = new TreeNode(val); root->left = createTree(vec);//创建左子树 root->right = createTree(vec);//创建右子树 } return root; } //切分字符串 void split(string str,vector<string>& vec) { int nPos = str.find( "," ); string strTmp; while( nPos > 0 ) { strTmp = str.substr( 0, nPos );//字串 vec.push_back( strTmp ); str.erase( 0, nPos+1 );//删除子串 nPos = str.find( "," ); } return; } };
中序遍历
中序遍历伪代码:
void inorderTraverse(TreeNode* root) { if (root == NULL) return; inorderTraverse(root->left);//递归左子树 // 中序遍历代码 inorderTraverse(root->right);//递归右子树 }
//中序遍历 //扩展的中序遍历结果不能唯一确定一棵二叉树 // 1 2 // / / \ // 2 3 1 // / // 3 //扩展的中序遍历均为#3#2#1#
后序遍历
后序遍历伪代码:
void postorderTraverse(TreeNode* root) { if (root == NULL) return; postorderTraverse(root->left);//递归左子树 postorderTraverse(root->right);//递归右子树 // 后序遍历代码 }
//后序遍历 class Codec { public: int index=0; //序列化 string serialize(TreeNode* root) { string str; PostOrderTraverse(str,root);//后序遍历 return str; } //后序遍历 void PostOrderTraverse(string& str,TreeNode* root) { if(!root) { str+="#,"; return; } PostOrderTraverse(str,root->left);//遍历左子树 PostOrderTraverse(str,root->right);//遍历右子树 str=str+to_string(root->val)+","; } //反序列化 TreeNode* deserialize(string str) { vector<string> vec; split(vec,str); index=vec.size()-1; return CreateTree(vec); } //根据扩展的后序遍历结果创建二叉树 //后序遍历的特点:生成树的字符串的最后一个字符,代表的就是它的根结点,倒数第二个就是它的右孩子 //从字符串后面开始推,按照根结点 -> 右结点 ->左节点 的顺序就能通过递归构造出一棵二叉树了 TreeNode* CreateTree(vector<string> vec) { if(index<0) return NULL; TreeNode* root=NULL; string str=vec[index--]; if(str!="#") { int val=atoi(str.c_str()); root=new TreeNode(val); root->right=CreateTree(vec);//创建右子树 root->left=CreateTree(vec);//创建左子树 } return root; } //切分字符串 void split(vector<string>& vec,string str) { int pos=str.find(","); string strTemp; while(pos>0) { strTemp=str.substr(0,pos); vec.push_back(strTemp); str.erase(0,pos+1); pos=str.find(","); } return; } };
层序遍历
层序遍历伪代码:
void traverse(TreeNode* root) { if (root == NULL) return; // 初始化队列,将 root 加入队列 queue<TreeNode*> queue; queue.push(root); while (!q.empty()) { TreeNode* cur = queue.pop(); //层级遍历代码 if (cur->left != NULL) q.push(cur.left); if (cur->right != NULL) q.push(cur.right); } }
//层序遍历,只适用于完全二叉树 class Codec { public: //序列化 string serialize(TreeNode* root) { string str; LevelOrderTraverse(str,root);//层序遍历 cout<<str<<endl; return str; } void LevelOrderTraverse(string& str,TreeNode* root) { if(!root) return; queue<TreeNode*> que; que.push(root); while(!que.empty()) { TreeNode* current=que.front(); que.pop(); str=str+to_string(current->val)+","; if(current->left!=NULL) que.push(current->left); if(current->right!=NULL) que.push(current->right); } } //反序列化 TreeNode* deserialize(string str) { vector<string> vec; split(vec,str); int index=0; return CreateTree(vec,index); } //根据扩展的层序遍历结果创建二叉树 TreeNode* CreateTree(vector<string> vec,int index) { if(index>=vec.size()) return NULL; TreeNode* root=NULL; string str=vec[index]; int val=atoi(str.c_str()); root=new TreeNode(val); root->left=CreateTree(vec,2*index+1); root->right=CreateTree(vec,2*index+2); return root; } //切分字符串 void split(vector<string>& vec,string str) { int pos=str.find(","); string strTemp; while(pos>0) { strTemp=str.substr(0,pos); vec.push_back(strTemp); str.erase(0,pos+1); pos=str.find(","); } return; } };