数据结构实习 - problem M 判断平衡二叉树

writer：pprp

date: 20171103

题目描述

给定一棵二叉树的中序和层序输出，判断是否为平衡二叉树的。如果是，输出YES如果不是输出NO。

输入

树结点个数

中序遍历序列

层序遍历序列

输出

是否是平衡二叉树的判断结论

样例输入

样例1：

1 2 3

2 1 3

样例2：

1 2 3 4

样例输出

样例1：

YES

样例2：

代码如下：

//M: 判别平衡二叉树

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

const int maxn = 1000;

int n;

struct tree

{

    tree * lchild;

    tree * rchild;

    int val;

    tree():lchild(NULL),rchild(NULL),val(0) {}

};

tree* createTree(int * layer, int * in,int n)

{

    if(n == 0)

        return NULL;

    int rin[maxn],lin[maxn],rlayer[maxn],llayer[maxn];

    memset(rin,0,sizeof(rin)),memset(lin,0,sizeof(lin));

    memset(rlayer,0,sizeof(rlayer)),memset(llayer,0,sizeof(llayer));

    tree * node = new tree;

    node->val = layer[0];

    int index = 0;

    for(index = 0 ; index < n ; index++)

        if(in[index] == layer[0])

            break;

    if(index == n)

    {

        cout << "Not found 404" << endl;

        return NULL;

    }

    int cnt = 0;

    for(int i = 0; i < index; i++)

        lin[cnt++] = in[i];

    cnt = 0;

    for(int i = index+1 ; i < n; i++)

        rin[cnt++] = in[i];

    int llayercnt = 0, rlayercnt = 0;

    for(int i = 1 ; i < n; i++)

    {

        for(int j = 0 ; j < index; j++)

        {

            if(lin[j] == layer[i])

                llayer[llayercnt++] = layer[i];

        }

    }

    for(int i = 1; i < n ; i++)

    {

        for(int j = 0 ; j < cnt; j++)

        {

            if(rin[j] == layer[i])

                rlayer[rlayercnt++] = layer[i];

        }

    }

    node->lchild = createTree(llayer,lin,llayercnt);

    node->rchild = createTree(rlayer,rin,rlayercnt);

    return node;

}

bool solve(tree * root, int& depth)

{

    if(root == NULL)

    {

        depth = 0;

        return true;

    }

    int leftdepth, rightdepth;

    bool bleft = solve(root->lchild,leftdepth);

    bool bright = solve(root->rchild,rightdepth);

    if(bleft && bright)

    {

        if(abs(leftdepth-rightdepth)<=1)

        {

            depth = 1+(leftdepth>rightdepth?leftdepth:rightdepth);

            return true;

        }

    }

    return false;

}

void post(tree * root)

{

    if(root != NULL)

    {

        post(root->lchild);

        post(root->rchild);

        cout << root->val << " ";

    }

}

int main()

{

    int n;

    cin >> n;

    int layer[maxn],in[maxn];

    for(int i = 0 ; i < n; i++)

        cin >> in[i];

    for(int j = 0 ; j < n ;  j++)

        cin >> layer[j];

    tree * root = createTree(layer,in,n);

    int depth = 0;

//    post(root);

//    cout << endl;

    if(solve(root,depth))

        cout << "Yes" << endl;

    else

        cout << "No" << endl;

    return 0;

}

巴特西

数据结构实习 - problem M 判断平衡二叉树

writer：pprp

date: 20171103

题目描述

输入

输出

样例输入

样例输出

最新文章

热门文章