두 갈래 나무의 앞, 중, 뒤, 단계를 비귀속 방식으로 인코딩합니다.
2927 단어 검지
두 갈래 나무만 복습하는 데 쓰인다
#include
using namespace std;
struct TreeNode {
int val;
int left;
int right;
}t[1000];
int vis[1000];
int ans[1000];
void preOrder(TreeNode root) {
stack q;
q.push(root);
int k = 0;
while(!q.empty()) {
TreeNode pNode = q.top();
q.pop();
ans[k++] = pNode.val;
if(pNode.right)
q.push(t[pNode.right]);
if(pNode.left)
q.push(t[pNode.left]);
}
}
void inOrder(TreeNode root) {
stack q;
q.push(root);
int k = 0;
memset(vis, 0, sizeof(vis));
vis[root.val] = 1;
while(!q.empty()) {
TreeNode pNode = q.top();
if(pNode.left && !vis[pNode.left]) {
q.push(t[pNode.left]);
} else {
q.pop();
ans[k++] = pNode.val;
vis[pNode.val] = 1;
if(pNode.right) {
q.push(t[pNode.right]);
}
}
}
}
void postOrder(TreeNode root) {
stack q, p;
q.push(root);
int k = 0;
while(!q.empty()) {
TreeNode pNode = q.top();
q.pop();
p.push(pNode);
if(pNode.left != 0)
q.push(t[pNode.left]);
if(pNode.right != 0)
q.push(t[pNode.right]);
}
while(!p.empty()) {
ans[k++]=p.top().val;
p.pop();
}
}
void Order(TreeNode root) {
queue q;
q.push(root);
int k=0;
while(!q.empty()) {
TreeNode now=q.front();
q.pop();
ans[k++]=now.val;
if(now.left!=0)
q.push(t[now.left]);
if(now.right!=0)
q.push(t[now.right]);
}
}
int main() {
int n;
while(~scanf("%d",&n)) {
memset(vis,0,sizeof(vis));
for(int i = 1; i <= n; i++) {
int a, b;
scanf("%d%d",&a,&b);
t[i].left=a;
t[i].right=b;
t[i].val=i;
vis[a]=1;
vis[b]=1;
}
int root;
for(int i = 1; i <= n; i++) {
if(vis[i] == 0) {
root = i;
break;
}
}
preOrder(t[root]);
for(int i = 0;i < n-1; i++) {
printf("%d ",ans[i]);
}
printf("%d
",ans[n-1]);
inOrder(t[root]);
for(int i = 0;i < n-1; i++) {
printf("%d ",ans[i]);
}
printf("%d
",ans[n-1]);
postOrder(t[root]);
for(int i = 0;i < n-1; i++) {
printf("%d ",ans[i]);
}
printf("%d
",ans[n-1]);
Order(t[root]);
for(int i = 0; i < n-1;i++) {
printf("%d ",ans[i]);
}
printf("%d
",ans[n-1]);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
검지 Offer - 두 갈래 트리 중 하나에 해당하는 경로(24)제목 설명 두 갈래 나무의 노드와 정수를 입력하고 두 갈래 나무의 결점 값과 정수를 입력하는 모든 경로를 출력합니다.경로는 나무의 뿌리 결점에서 시작하여 잎 결점까지 내려가는 결점으로 경로를 형성합니다.(주의: 값을...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.