[검지 오퍼] 8.두 갈래 나무를 재건하다
두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 역행 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 역행 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 뒷 순서 역행 시퀀스를 출력합니다.
코드
/*--------------------------------------- * :2015-07-20 * :SJF0115 * : 8. * :AC * :http://www.nowcoder.com/books/coding-interviews/8a19cbe657394eeaac2f6ea9b0f6fcf6?rp=1 * : Offer * : -----------------------------------------*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};
class Solution{
public:
struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
int size = pre.size();
if(size == 0){
return nullptr;
}//if
return PreInBuildTree(pre,in,0,0,size);
}
private:
TreeNode* PreInBuildTree(vector<int> preorder,vector<int> inorder,int preIndex,int inIndex,int size){
if(size == 0){
return nullptr;
}//if
//
TreeNode* root = new TreeNode(preorder[preIndex]);
//
int index = 0;
for(int i = 0;i < size;++i){
// :inorder[inIndex+i]
if(preorder[preIndex] == inorder[inIndex+i]){
index = inIndex+i;
break;
}//if
}//for
//
int leftSize = index - inIndex;
//
int rightSize = size - leftSize - 1;
//
root->left = PreInBuildTree(preorder,inorder,preIndex+1,inIndex,leftSize);
//
root->right = PreInBuildTree(preorder,inorder,preIndex+1+leftSize,index+1,rightSize);
return root;
}
};
void PostOrder(TreeNode* root){
if(root){
PostOrder(root->left);
PostOrder(root->right);
cout<<root->val<<endl;
}//if
}
int main(){
Solution s;
vector<int> preOrder = {1,2,4,7,3,5,6,8};
vector<int> inOrder = {4,7,2,1,5,3,8,6};
TreeNode* root = s.reConstructBinaryTree(preOrder,inOrder);
PostOrder(root);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
전차와 중차에 따라 두 갈래 트리-java판을 구성하다package offer; class TreeNode{ public int value; public TreeNode left; public TreeNode right; public TreeNode(int value,...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.