首页 > 试题广场 >

二叉树的反序列化

[编程题]二叉树的反序列化

热度指数：76 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于一棵二叉树我们定义它的括号序列为满足如下条件的序列：对于一个节点生成一个括号，括号内是其子树的括号序列，其中左儿子(若存在)的括号在前，右儿子(若存在)的括号在后。同时为了避免重复，我们采用树的最小表示，即若一个节点只有一个儿子，那么这个儿子必为左儿子。给定一个括号序列，请将其反序列化为一棵树。

给定一个字符串A，代表括号序列。请返回反序列化后树的根节点指针，树中节点的值按生成节点的次序从1开始标号。

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

zyweng


	/*



	本题是希望通过括号序列得到先序遍历的二叉树，因此只需要按照先序遍历的要求从左子树开始构造。关键的问题是如何处理



	括号，即找到对应的左右括号。这里采用了栈的方法，当左括号入栈后出现第一次栈为空，则说明找到一个完整的括号序列，



	也即一个结点，可以获取左右子树的括号范围。



	*/



	classSequenceToTree {



	public:



	    TreeNode* toTree(string A) {



	        // write code here



	        TreeNode *root = NULL;



	        intvalue = 1;



	        if(A.empty()) returnNULL;



	        v = 1;



	        CreateTree(A,root,0,A.size()-1);



	        returnroot;



	    }



	    voidCreateTree(string A,TreeNode*& root,intleft,intright){



	        intj;



	        stack<char> sNode;



	        cout<<"left: "<<left<<" right: "<<right<<endl;



	        if(left>=right) return;



	        root = newTreeNode(v++);



	        j = left;



	        do{



	            if(j+1<right){



	                if(A[j+1] == '(')



	                    sNode.push(A[j]);



	                else{



	                    sNode.pop();



	                }



	                j++;



	            }



	        }while(!sNode.empty());



	        CreateTree(A,root->left,left+1,j);



	        CreateTree(A,root->right,j+1,right-1);



	    }



	private:



	    intv;



	};