PAT甲级-1119 Pre- and Post-order Traversals

题目

题目大意

已知一棵树的先序遍历和后序遍历，求这个树的中序遍历。如果结果唯一，输出Yes，如果不唯一，输出No，遍历结果输出任何一种都可以。

思路

由先序和后序构建一棵树，首先要理解先序和后序的遍历过程。先序是根左右，后序是左右根，可以看出，两者最大的不同就是根节点的位置。先序的根节点是在一棵树的最前面，后序的根节点是在树的最后面。遍历时需要两个先序指针ql，qr和后序指针hl，hr分别确定树的范围。

首先从先序中锁定根节点，即先序遍历的第一个节点（在ql-qr范围内），将这个根节点插入树，然后开始找这个根节点的左右子节点。先找左子节点（左子树的根节点），先序第二个节点就是leftRoot，接着从后序中找到与该节点值相同的节点位置pos，pos即是左子树的最后一个节点（后序的根节点是在树的最后面），就确定了左子树的范围（hl-pos）。确定完左子树的范围，右子树的范围就好确定了。

注意，在确定树的范围过程中，不要随意改变ql，qr，hl，hr的值，而用新变量pos来确定。

判读一棵树是否唯一，即当某根节点只有一个孩子节点时，不能确定该孩子节点是左孩子还是右孩子，因此就不唯一。将这种情况代入构造树的过程，如果根节点的左孩子和右孩子相同，就表明这个根节点只有一个孩子节点，也即先序的第二个节点（leftRoot）等于后序的倒数第二个节点（rightRoot）时，该树不唯一。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<int> q;  // 前序遍历
vector<int> h;  // 后序遍历
vector<int> z;  // 中序遍历
bool isUnique = true;  // 是否唯一

struct node {
    int data;
    node *lchild, *rchild;
};

void buildTree(node *&root, int ql, int qr, int hl, int hr) {
    if (ql > qr || hl > hr) {
        return;
    }
    root = new node();  // 插入根节点
    root->data = q[ql];
    root->lchild = root->rchild = nullptr;
    if (ql == qr) {
        return;
    }  // 只有根，没有孩子，是叶子节点，返回

    int leftRoot = q[ql + 1];  // 左子树的根节点
    int pos = hl;
    while (pos <= hr && h[pos] != leftRoot) {
        pos++;
    }  // 确定左子树的右边界pos

    if (leftRoot == h[hr - 1]) {  // 检查树是否唯一
        isUnique = false; // 如果前序的第二个节点（根的左子树节点）是后序遍历倒数第二个节点（根的右子树节点），左子树和右子树节点是同一个，说明只有一个孩子
        buildTree(root->lchild, ql + 1, qr, hl, hr - 1);  // 将这个孩子作为左孩子或右孩子均可，在此处将其作为左孩子
    } else {
        int leftSize = pos - hl + 1;
        buildTree(root->lchild, ql + 1, ql + leftSize, hl, pos);
        buildTree(root->rchild, ql + leftSize + 1, qr, pos + 1, hr - 1);
    }
}

void traverseTree(node *root) {
    if (root) {
        traverseTree(root->lchild);
        z.push_back(root->data);
        traverseTree(root->rchild);
    }
}

int main() {
    cin >> n;
    q.resize(n);
    h.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> q[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    node *root = nullptr;
    buildTree(root, 0, n - 1, 0, n - 1);
    traverseTree(root);
    cout << (isUnique ? "Yes" : "No") << endl;  // 这种写法更简洁，注意要加括号
    for (int i = 0; i < z.size(); i++) {
        cout << z[i];
        if (i != z.size() - 1) {
            cout << " ";
        }
    }
    cout << endl;

    return 0;
}
/*
    之所以要确定左子树的右边界，是因为前序遍历和后序遍历的特性。前序是根左右，后序是左右根，
    两者主要的不同就在于根节点的顺序不同。先确定前序一个左子树的根，再在后续中找到该根的对
    应位置pos，那么这个位置前面输出的节点(hl-pos)就是它的孩子节点，那么这个pos也就是这个
    左子树的右边界。这样就可以区分左右子树的范围了。
*/

原文地址：https://blog.csdn.net/weixin_74092648/article/details/142583701

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！