列表

详情

NC200380. 二叉查找树

描述

树神精通各种树，这其中自然包括二叉查找树

立志成为小树神的cjc正在向树神学习一手二叉查找树，他问了这么一道题：将一些数顺序插入建立二叉查找树，有多少种形状不同的子树？

如果你精通数据结构，可以跳过以下内容。

二叉查找树，也称为二叉搜索树、有序二叉树或排序二叉树。它是一种具有如下性质的二叉树形结构
1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值
3. 任意节点的左、右子树也分别为二叉查找树
4. 没有值相等的节点。
一列数按顺序插入二叉查找树的构造方法如下
1. 若当前树为空，则加入节点，值为当前数的值，该节点视为根节点
2. 若当前树不为空，则从根节点开始向下遍历。若当前数的值小于正在遍历的节点值，则向左子节点遍历，否则向右子节点遍历，直到不存在对应的子节点为止，在该处建立新的节点，值为当前数的值。

其中，树形结构在计算机学科中，一般指一种看起来像一棵倒挂的树的层次结构，如图1

树形结构具有如下性质

1. 每个节点都只有有限个子节点或无子节点
    1.1 对于二叉树，每个节点都只有0~2个子节点
2. 没有父节点的节点称为根节点
3. 每一个非根节点有且只有一个父节点
4. 除了根节点外，每个子节点可以分为多个不相交的子树
5. 树里面没有环路

其中，子树指的是树形结构中，任意节点及其所有后代导出的子结构。二叉树左子树就是以当前节点看，它的左子节点那一分支的子树，该子树以当前节点左子节点为根。右子树就是以当前节点看，它的右子节点那一分支的子树，该子树以当前节点右子节点为根。

对于两颗二叉树子树，若忽略节点上的值，得到相同的树形结构，则认为这两颗二叉树子树形状相同。


输入描述

第一行输入一个正整数，代表要插入的数的个数

第二行输入n个正整数，一个1~n的排列，即1~n中每个数仅出现一次。

输出描述

按输入顺序将数依次插入二叉查找树，输出这颗二叉查找树互不相同的子树个数。

示例1

输入: 

4
1 2 3 4

输出: 

4

示例2

输入: 

4
1 3 4 2

输出: 

3

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 1272K, 提交时间: 2019-12-14 17:30:13 

#include<bits/stdc++.h>
using namespace std;
const int MX=1e5+9;
int a[MX],l[MX],r[MX],tot=0,n;
map<pair<int,int>,int> mp;

void fin(int x,int k){
    if( a[x]<=a[k] ){
        if( r[x]==-1 ){
            r[x]=k;
            return ;
        }
        fin(r[x],k);
    }
    else{
        if( l[x]==-1 ){
            l[x]=k;
            return ;
        }
        fin(l[x],k);
    }
}

int dfs(int x){
    int L=-1,R=-1;
    if( l[x]!=-1 )
        L=dfs(l[x]);
    if( r[x]!=-1 )
        R=dfs(r[x]);
    if( !mp.count({L,R}) ) mp[{L,R}]=++tot;
    return mp[{L,R}];
}

int main()
{
   // freopen("input.txt","r",stdin);
    scanf("%d",&n);
    for( int i=1 ; i<=n ; i++ )
        scanf("%d",&a[i]);
    memset(l,-1,sizeof(l));
    memset(r,-1,sizeof(r));
    for( int i=2 ; i<=n ; i++ )
        fin(1,i);
    dfs(1);
    printf("%d\n",tot);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 460K, 提交时间: 2019-12-19 01:00:16 

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4;
map<pair<int,int>,int>vis;
int A[N],rt,ls[N],rs[N],val[N],tot,n;
void Insert(int &o,int v){
    if(!o){o=++tot;val[o]=v;return;}
    if(v>val[o])Insert(rs[o],v);
    else Insert(ls[o],v);
}
int ans;
int dfs(int o){
    int lson=-1,rson=-1;
    if(ls[o])lson=dfs(ls[o]);
    if(rs[o])rson=dfs(rs[o]);
    if(vis.count({lson,rson})==0)vis[{lson,rson}]=++ans;
    return vis[{lson,rson}];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&A[i]);
        Insert(rt,A[i]);
    }
    dfs(rt);
    printf("%d\n",ans);
}

上一题

© 2024 nowcoder.com