团体程序设计天梯赛-练习集 L2 （树）

L2-004 这是二叉搜索树吗？ (25 分)

• 由于这道题的权值不是distinct，说明有相同权值的点，在二叉搜索树中左子树的权值严格小于根节点，因此，对于二叉搜索树来说，在中序遍历中找根节点的位置应该从左开始第一个，而在二叉搜索树的镜像（中序遍历为从大到小），在中序遍历中找根节点的位置应该从右开始第一个

#include 
#include 
using namespace std;
const int N = 1e3 + 10;

int inorder[N], preorder[N];
int postorder[N], cnt;

bool build(int il, int ir, int pl, int pr, int type) {
    if (il > ir) return true;
    int root = preorder[pl];
    int k;
    if (!type) {
        for (k = il; k <= ir; ++ k) {
            if (inorder[k] == root) {
                break;
            }
        }
        if (k > ir) return false;
    } else {
        for (k = ir; k >= il; -- k) {
            if (inorder[k] == root) {
                break;
            }
        }
        if (k < il) return false;
    }
    bool ok = true;
    if (!build(il, k - 1, pl + 1, pl + 1 + k - 1 - il + 1 - 1, type)) ok = false;
    if (!build(k + 1, ir, pl + 1 + k - 1 - il + 1 - 1 + 1, pr, type)) ok = false;
    postorder[cnt ++ ] = root;
    return ok;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++ i) {
        cin >> preorder[i];
        inorder[i] = preorder[i];
    }
    sort(inorder, inorder + n);
    if (build(0, n - 1, 0, n - 1, 0)) {
        cout << "YES" << endl;
        for (int i = 0; i < n; ++ i) {
            if (i != 0) cout << ' ';
            cout << postorder[i];
        }
    } else {
        reverse(inorder, inorder + n);
        cnt = 0;
        if (build(0, n - 1, 0, n - 1, 1)) {
            cout << "YES" << endl;
            for (int i = 0; i < n; ++ i) {
                if (i != 0) cout << ' ';
                cout << postorder[i];
            }
        } else {
            cout << "NO";
        }
    }
}

L2-006 树的遍历 (25 分)

• 层序遍历需要从根节点开始，因此在建树过程中，返回值为root
• 由于保证权值distinct，因此，用pos数组来记录位置，就不用每次遍历去寻找位置
• 这里如果不用unordered_map改用数组会wa一个点和段错误一个点
• map中查找是否拥有这个键 count，如果不等于0说明有
• 注意k > il才有左儿子

#include 
#include 
using namespace std;
const int N = 40;

int postorder[N], inorder[N];
int q[N];
unordered_map<int, int> l, r, pos;

int build(int il, int ir, int pl, int pr) {
    int root = postorder[pr];
    int k = pos[root];
    if (k > il) l[root] = build(il, k - 1, pl, pl + k - 1 - il + 1 - 1);
    if (k < ir) r[root] = build(k + 1, ir, pl + k - 1 - il + 1 - 1 + 1, pr - 1);
    return root;
}
void bfs(int root) {
    int hh = 0, tt = 0;
    q[tt ++ ] = root;
    while (hh <= tt) {
        int t = q[hh ++ ];
        if (l.count(t)) q[tt ++ ] = l[t];
        if (r.count(t)) q[tt ++ ] = r[t];
    }
    for (int i = 0; i < tt; ++ i) {
        if (i != 0) cout << ' ';
        cout << q[i];
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        cin >> postorder[i];
    }
    for (int i = 1; i <= n; ++ i) {
        cin >> inorder[i];
        pos[inorder[i]] = i;
    }
    int root = build(1, n, 1, n);
    bfs(root);
}

L2-011 玩转二叉树 (25 分)

#include 
#include 
using namespace std;
const int N = 40;

int inorder[N], preorder[N];
int q[N];
unordered_map<int, int> pos, l, r;

int build(int il, int ir, int pl, int pr) {
    int root = preorder[pl];
    int k = pos[root];
    if (k > il) r[root] = build(il, k - 1, pl + 1, pl + 1 + k - 1 - il + 1 - 1);
    if (k < ir) l[root] = build(k + 1, ir, pl + 1 + k - 1 - il + 1 - 1 + 1, pr);
    return root;
}
void bfs(int root) {
    int hh = 0, tt = 0;
    q[tt ++ ] = root;
    while (hh <= tt) {
        int t = q[hh ++ ];
        if (l.count(t)) q[tt ++ ] = l[t];
        if (r.count(t)) q[tt ++ ] = r[t];
    }
    for (int i = 0; i < tt; ++ i) {
        if (i != 0) cout << ' ';
        cout << q[i];
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        cin >> inorder[i];
        pos[inorder[i]] = i;
    }
    for (int i = 1; i <= n; ++ i) {
        cin >> preorder[i];
    }
    int root = build(1, n, 1, n);
    bfs(root);
}