递归 | 1020 Tree Traversals （25 po

1020 Tree Traversals

思路

当前树的后序post_seq最左、最右下标pll, prr
当前树的中序in_seq最左、最右下标ill, irr

1. 对后序（ 左右根 ）：末尾post_seq[prr]为根，value为r_value
2. 对中序（ 左根右 ）：在中序找到r_value( 根 )，下标为ind，则它的左子树的中序[ill, ind - 1],右子树的中序[ind + 1, irr]。
   左子树节点数量l_size = ind - ill
   右子树节点数量r_size = irr - ind
3. 划分后序：
   左子树[pll, pll + l_size - 1]  右子树[pll+ l_size, prr]

level的获取也是依靠递归，类似递归获取树的高度的方式。

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
int nn, post_seq[32], in_seq[32];
vector<pair<int, int>> level_seq; //value, level

int get_level(int ill, int irr, int pll, int prr, int level) {
    if (irr < ill) {
        return level - 1;
    }
    int father_value = post_seq[prr];
    int cut;
    for (int i = ill; i <= irr; ++i) {
        if (in_seq[i] == father_value) {
            cut = i;
            break;
        }
    }
    level_seq.push_back(make_pair(father_value, level));
    //update pll,prr,ill,irr
    int left_len = cut - ill;
    int level_l = get_level(ill, cut - 1, pll, pll + left_len - 1, level + 1);
    int level_r = get_level(cut + 1, irr, pll + left_len, prr - 1, level + 1);
    return max(level_l, level_r);
}

int main() {
    scanf("%d", &nn);
    for (int i = 0; i < nn; ++i) {
        scanf("%d", &post_seq[i]);
    }
    for (int i = 0; i < nn; ++i) {
        scanf("%d", &in_seq[i]);
    }
    int height = get_level(0, nn - 1, 0, nn - 1, 0);
    for (int i = 0, j = 0; i < nn && j <= height; ++j) {
        for (int k = 0; k < nn; ++k) {
            if (level_seq[k].second == j) {
                if (i == nn - 1)
                    printf("%d", level_seq[k].first);
                else {
                    printf("%d ", level_seq[k].first);
                    i++;
                }
            }
        }
    }
    return 0;
}

相关

• 已知后序、中序，求前序
• 已知后序、中序，构建二叉树