首页 > 代码库 > PAT甲题题解1099. Build A Binary Search Tree (30)-二叉树遍历
PAT甲题题解1099. Build A Binary Search Tree (30)-二叉树遍历
题目就是给出一棵二叉搜索树，已知根节点为0，并且给出一个序列要插入到这课二叉树中，求这棵二叉树层次遍历后的序列。
用结构体建立节点，val表示该节点存储的值，left指向左孩子，right指向右孩子。中序遍历的顺序正好是序列从小到大的顺序，因此中序遍历的时候顺便赋值就可以了，最后层次遍历输出。
思路一：中序遍历的时候赋值
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> #include <queue> #define LEFT 0 #define RIGHT 1 using namespace std; const int maxn=105; int cnt=0; /* 中序遍历的顺序即为序列从小到大的顺序，因此中序遍历的时候顺便赋值， 最后层次遍历输出即可。 */ struct Node{ int val; int left; int right; }node[maxn]; void dfs(int i,int*a){ if(i==-1) return; dfs(node[i].left,a); node[i].val=a[cnt]; cnt++; dfs(node[i].right,a); } int main() { int n,l,r; int a[maxn]; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d %d",&l,&r); node[i].left=l; node[i].right=r; } for(int i=0;i<n;i++){ scanf("%d",&a[i]); } sort(a,a+n); dfs(0,a); queue<Node>q; q.push(node[0]); bool first=true; while(!q.empty()){ Node tmp=q.front(); q.pop(); if(first){ printf("%d",tmp.val); first=false; } else{ printf(" %d",tmp.val); } if(tmp.left!=-1) q.push(node[tmp.left]); if(tmp.right!=-1) q.push(node[tmp.right]); } return 0; }
思路二：两次dfs
这是我最开始的解题思路，复杂化了，不过好歹一次就AC了。
节点leftnum存储它的左子树的节点个数，rightnum存储它的右子树的节点个数，num存储以该节点为根节点的子树的节点个数。smallernum则是存储值比它小的节点个数。id代表了该节点是其父亲节点的左孩子还是右孩子，father是其父节点。
这样我们就能根据smallernum来判断该节点在序列（从小到大排列）中的位置。
第一次dfs把leftnum、rightnum、num给求出来。
第二次dfs则是计算smallernum，这里要分两种情况来考虑。
1.节点i为左孩子
那么往上追溯祖先节点，直到第一个id为右孩子的节点p，那么节点i的smallernum则为：
p的父亲节点的smallernum+1（即p的父亲节点）+节点i的左子树个数
2.节点i为右孩子
那么节点i的smallernum则为：
其父亲节点的smallernum+1（其父亲节点）+节点i的左子树个数。
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> #include <queue> #define LEFT 0 #define RIGHT 1 using namespace std; const int maxn=105; struct Node{ int id; int val; int father; int left; int right; int leftnum; //the number of left subtree int rightnum; int smallernum; //the number of left nodes,not only left subtree. int num; //the number of this subtree }node[maxn]; /* calculate leftnum and num */ int dfsNum(int i){ if(i==-1) return 0; int l=node[i].left; int r=node[i].right; if(i==0){ node[i].id=LEFT; node[i].father=-1; } if(l!=-1){ node[l].id=LEFT; node[l].father=i; } if(r!=-1){ node[r].id=RIGHT; node[r].father=i; } node[i].leftnum=dfsNum(l); node[i].rightnum=dfsNum(r); node[i].num=node[i].leftnum+node[i].rightnum+1; return node[i].num; } void dfsSmallerNum(int i){ if(i==-1) return ; int l=node[i].left; int r=node[i].right; dfsSmallerNum(l); node[i].smallernum=0; if(node[i].id==LEFT){ int p=node[i].father; while(p!=-1){ if(node[p].id==RIGHT) break; p=node[p].father; } if(l!=-1) node[i].smallernum+=node[l].num; if(p>0){ node[i].smallernum+=node[node[p].father].smallernum+1; } } else{ if(l!=-1) node[i].smallernum+=node[l].num; if(i>0) node[i].smallernum+=node[node[i].father].smallernum+1; } dfsSmallerNum(r); } int main() { int n,l,r; int a[maxn]; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d %d",&l,&r); node[i].left=l; node[i].right=r; } for(int i=0;i<n;i++){ scanf("%d",&a[i]); } sort(a,a+n); dfsNum(0); dfsSmallerNum(0); int res[maxn]; for(int i=0;i<n;i++){ //printf("%d smaller:%d left:%d right:%d num:%d\n",i,node[i].smallernum,node[i].leftnum,node[i].rightnum,node[i].num); int p=node[i].smallernum; node[i].val=a[p]; } queue<Node>q; q.push(node[0]); bool first=true; while(!q.empty()){ Node tmp=q.front(); q.pop(); if(first){ printf("%d",tmp.val); first=false; } else{ printf(" %d",tmp.val); } if(tmp.left!=-1) q.push(node[tmp.left]); if(tmp.right!=-1) q.push(node[tmp.right]); } return 0; }
PAT甲题题解1099. Build A Binary Search Tree (30)-二叉树遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。