[검지 Offer] 두 갈래 트리 재구성(전순 시퀀스와 중간 시퀀스, 두 갈래 트리 재구성)
2196 단어 ACM_두 갈래 나무검지 Offer검지offer
제목 링크
제목 설명
두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 반복 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 되돌려줍니다.
두 갈래 나무 훑어보는 방식:
선행 시퀀스: 루트 노드를 먼저 방문하고 왼쪽 하위 노드를 방문하며 마지막으로 오른쪽 하위 노드를 방문합니다.
중서 서열: 먼저 왼쪽 노드를 방문하고 루트 노드를 방문하고 마지막으로 오른쪽 노드를 방문한다.
뒷순서 시퀀스: 왼쪽 노드를 먼저 방문하고 오른쪽 노드를 방문하며 마지막으로 루트 노드를 방문합니다.
층차 서열: 순서대로 두 갈래 나무에서 아래로, 각 층은 왼쪽에서 오른쪽으로 접근한다.
교대 층차: 두 갈래 나무에서 아래로, 각 층마다 교대 (왼쪽에서 오른쪽 또는 오른쪽에서 왼쪽으로) 방문한다.
사고방식: 이상의 역행 방식을 알고 나면 앞의 서열의 첫 번째 원소와 뒤의 마지막 노드가 뿌리 노드라는 것을 알 수 있다. 그리고 중서 서열에서 뿌리 노드를 찾을 수 있다. 그림을 그리면 좌우 트리의 구축으로 나눌 수 있다. 그러면 역귀로 해결할 수 있다.
코드:
#include
#include
using namespace std;
/**
Definition for binary tree
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x): val(x), left(NULL), right(NULL) {}
};
*/
class Solution {
public:
TreeNode* reConstructBinaryTree(vector pre,vector vin) {
int len=pre.size();
if(len==0) {
return NULL;
}
TreeNode* res=new TreeNode(pre[0]);
//cout<lpre,rpre,lvin,rvin;
for(int i=1; ileft=reConstructBinaryTree(lpre,lvin);
res->right=reConstructBinaryTree(rpre,rvin);
return res;
}
};
/*
int main() {
int ppre[8]= {1,2,4,7,3,5,8,6};
int vvin[8]= {4,7,2,1,5,3,8,6};
vectorpre(ppre,ppre+8);
vectorvin(vvin,vvin+8);
Solution sol;
sol.reConstructBinaryTree(pre,vin);
return 0;
}*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[검지 Offer] 두 갈래 트리 재구성(전순 시퀀스와 중간 시퀀스, 두 갈래 트리 재구성)두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
