首页 > 代码库 > 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;
}
View Code

 

 

思路二:两次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;
}
View Code

 

PAT甲题题解1099. Build A Binary Search Tree (30)-二叉树遍历