【数据结构】二叉树判断--同一棵二叉树？

叶茂林

发布于 2023-07-30 13:21:40

1370

发布于 2023-07-30 13:21:40

文章被收录于专栏：叶子的开发者社区

题目描述

二叉树分别以数组存储方式创建、以先序遍历序列创建。输入二叉树的数组存储、先序遍历结果，判断根据它们创建的二叉树是否是同一棵二叉树。

输入

测试次数t

每组测试数据两行：

第一行：二叉树的数组存储（英文字母表示树结点，#表示空树）

第二行：二叉树的先序遍历结果(英文字母表示树结点，#表示空树）

输出

对每组测试数据，如果两种方式创建的是同一棵二叉树，输出YES，否则，输出NO。

输入样例1

3 ABCDE ABD##E##C## ABC##DE####W##F AB##CDW###E#F## abc##d ab##c#d##

输出样例1

YES YES NO

思路分析

这道题真是让人哭笑不得，我原本写了一个AC代码，就是下面的代码1，然后和同学交流的时候，我突然想到这个代码其实是不满足要求的，能AC纯粹是因为后台测试数据太拉，如果能加上一个三层空树，那么下面这个代码是跑不过的。

下面让我们仰望一下大佬的代码，就是下面的代码2，这是我的学长助教写的，当然我根据他的代码思路写的，不完全一样，但这并不妨碍我们感受其中的美妙，直接根据顺序存储的序列先序遍历还原，然后直接进行比较，NB，orz。

AC代码

#include <iostream>
#include <string>
#include <queue>

using namespace std;

class BiTreeNode {
public:
    char data;                    //数据域
    BiTreeNode *leftChild, *rightChild;    //左右子树指针
    BiTreeNode() : leftChild(NULL), rightChild(NULL) {}
    ~BiTreeNode() {}
};

class BiTree {
private:
    BiTreeNode *root;    //根结点指针
    string sTree,order;        //建树字符串
    int pos;            //标识建树字符串的当前字符位置
    BiTreeNode *CreateTree() {//建树私有函数
        if (pos == sTree.size()) {
            return NULL;
        } else if (sTree[pos] == '#') {
            BiTreeNode *T = new BiTreeNode();
            T->data = sTree[pos++];
            T->leftChild = NULL;
            T->rightChild = NULL;
            return T;
        }
        BiTreeNode *T = new BiTreeNode();
        T->data = sTree[pos++];
        T->leftChild = CreateTree();
        T->rightChild = CreateTree();
        return T;
    }
public:
    BiTree() : root(NULL) {};
    void Create(string vArray) {//建树公有接口，参数是特定的先序遍历字符串
        pos = 0;
        sTree.assign(vArray);    //把参数保存到内部字符串
        root = CreateTree();    //建树成功后root指向根结点
    }
    void LevelOrder(BiTreeNode *T) {
        queue<BiTreeNode *> open;
        BiTreeNode *p = T;
        if (p)
            open.push(p);
        while (!open.empty()) {
            p = open.front();
            open.pop();
            if (p) {
                order += p->data;
                open.push(p->leftChild);
                open.push(p->rightChild);
            } else order += '#';
        }
    }

    void Show(string &order) {
        LevelOrder(root);
        if (order == this->order.substr(0, order.size()))
            cout << "YES" << endl;
        else cout << "NO" << endl;
    }
};

int main() {
    int t;
    string temp, order;
    cin >> t;
    while (t--) {
        cin >> order >> temp;
        BiTree tree;
        tree.Create(temp);
        tree.Show(order);
    }
    return 0;
}

膜拜大佬代码

#include <iostream>

using namespace std;

void rebuild(int i, string &test, string &order) {
    if (i >= order.size() || order[i] == '#') {
        test += '#';
        return;
    }
    test += order[i];
    rebuild(2 * i + 1, test, order);
    rebuild(2 * i + 2, test, order);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string order, pre, test;
        cin >> order >> pre;
        rebuild(0, test, order);
        if (pre == test)
            cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-11-07，如有侵权请联系 cloudcommunity@tencent.com 删除

存储