검 지 offer - 이 진 트 리 재건
8929 단어 알고리즘프로 그래 밍 문제 de 세계
이 진 트 리 의 앞 순 서 를 입력 하고 중간 순 서 를 옮 겨 다 니 는 결 과 를 입력 하 십시오. 이 이 진 트 리 를 다시 만 드 십시오.입력 한 앞 순서 와 중간 순 서 를 옮 겨 다 니 는 결과 에 중복 되 는 숫자 가 없다 고 가정 합 니 다.예 를 들 어 앞 순서 옮 겨 다 니 기 시퀀스 {1, 2, 4, 7, 3, 5, 6, 8} 과 중간 순서 옮 겨 다 니 기 시퀀스 {4, 7, 2, 1, 5, 3, 8, 6} 을 입력 하면 이 진 트 리 를 다시 만 들 고 돌아 갑 니 다.
블 로그 의 코드 는 모두 우 객 C + + 11 (clang + 3.9) 에서 통과 되 었 다.
처음 이 문 제 를 풀 었 을 때 정말 갈 피 를 잡 을 수 없 었 습 니 다. 주로 앞 순서 와 중 서 를 옮 겨 다 니 는 특징 을 이해 하지 못 했 습 니 다. 나중에 소 손님 이 쓴 코드 를 보고 나 서 야 갑자기 밝 아 졌 습 니 다. 그 다음 에 구체 적 으로 설명 하 겠 습 니 다.
먼저, 앞 순 서 를 옮 겨 다 니 는 첫 번 째 숫자 는 바로 이 진 트 리 뿌리 노드 의 값 이 고 중간 순 서 는 중간 에 있 으 며 왼쪽 은 왼쪽 서브 트 리 의 값 이 고 오른쪽 은 오른쪽 서브 트 리 의 값 이 며 이 특성 을 결합 하여 이 진 트 리 를 재건 하 는 것 을 알 아야 한다.
코드 는 다음 과 같 습 니 다:
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
// ， nullptr
if(0 == pre.size() || 0 == vin.size())
return nullptr;
// ，
TreeNode* ret = reConstructBinaryTree1(pre,0,pre.size()-1,vin,0,vin.size()-1);
return ret;
}
public:
TreeNode* reConstructBinaryTree1(vector<int> pre,int p1,int p2,vector<int> vin,int v1,int v2)
{
// ， nullptr
if(p1>p2 || v1>v2)
return nullptr;
// ，
TreeNode* root = new TreeNode(pre[p1]);
// ，
for(int i=v1;i<=v2;++i)
{
if(pre[p1] == vin[i])
{
// ， ( i-v1 ) ( )
root->left = reConstructBinaryTree1(pre,p1+1,p1+i-v1,vin,v1,i-1);
// ， ( i-v1+1 ) ( )
root->right = reConstructBinaryTree1(pre,p1+i-v1+1,p2,vin,i+1,v2);
}
}
return root;
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
