根据中序和前序遍历构建二叉树

秒速五厘米 2022-06-17 06:46 181阅读 0赞

面试题6：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历都不含重复的数字

BinaryTreeNode* constructCore(int* startPreOrder,int* endPreOrder,int* startInOrder,int* endInOrder){
    
    	int rootValue = startPreOrder[0];
    	BinaryTreeNode* root = new BinaryTreeNode();
    	root->m_nValue = rootValue;
    	root->m_pLeft=NULL;
    	root->m_pRight=NULL;
    	
    	int* rootInorder=startInOrder;
    	for(;*rootInorder!=rootValue&&rootInorder<=endInOrder;rootInorder++);
    
    	if(rootInorder>endInOrder||*rootInorder!=rootValue){
    		throw std::exception("invalid input");
    	}
    	//左子树长度
    	int leftLength=rootInorder-startInOrder;
    	int* leftPreOrderend=startPreOrder+leftLength;
    	if(startPreOrder==endPreOrder){
    		if(startInOrder==endInOrder&&*startInOrder==*startInOrder)
    			return root;
    		else 
    			throw std::exception("Invalid Input!");
    	}
    	//构建左子树
    	if(leftLength>0)
    	root->m_pLeft = constructCore(startPreOrder+1,leftPreOrderend,startInOrder,rootInorder-1);
    	//构建右子树
    	if(leftLength<endInOrder-startInOrder)//右子树长度不为0
    	root->m_pRight = constructCore(leftPreOrderend+1,endPreOrder,rootInorder+1,endInOrder);
    	return root;
    
    }
    BinaryTreeNode* construct(int* preOrder,int* inOrder,int length){
    
    	if(preOrder==NULL||inOrder==NULL||length<=0)return NULL;
    
    	return constructCore(preOrder,preOrder+length-1,inOrder,inOrder+length-1); 
    
    }

参考：剑指offer 何海涛