二叉树构建与遍历 - Tree Traversals

我采用经典思路：构建二叉树、然后再进行层序遍历。思路很简单，构建过程也是很基础。
柳神的思路很特殊，值得对照思考。链接在此

// runtime: 4ms
// space: 384K
// https://pintia.cn/problem-sets/994805342720868352/problems/994805485033603072
#include <cstdio>
#include <queue>
using namespace std;

const int MAXN = 32;
int post[MAXN];
int in[MAXN];

struct TreeNode {
    int data;
    TreeNode* leftChild;
    TreeNode* rightChild;
    TreeNode(int n): data(n), leftChild(NULL), rightChild(NULL) {}
};
// 二叉树构建
TreeNode* Build(int root, int start, int end) {
    if (start > end) // 退出标志
        return NULL;
    int i = start;
    while (i < end && in[i] != post[root]) i++;
    TreeNode* tree = new TreeNode(post[root]);
    tree->leftChild = Build(root - end + i - 1, start, i - 1); // 计算边界
    tree->rightChild = Build(root - 1, i + 1, end); // 计算边界
    return tree;
}
// 层序遍历
void LevelTraversal(TreeNode* root, int n) {
    int i = 0;
    queue<TreeNode*> q;
    if (root != NULL) {
        q.push(root);
    }

    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();
        if(i++ < n - 1)
            printf("%d ", current->data);
        else
            printf("%d", current->data);

        if (current->leftChild != NULL) {
            q.push(current->leftChild);
        }
        if (current->rightChild != NULL) {
            q.push(current->rightChild);
        }
    }
}

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%d", &post[i]);
    }
    for (int i = 0; i < N; ++i) {
        scanf("%d", &in[i]);
    }
    TreeNode* root = Build(N - 1, 0, N - 1);
    LevelTraversal(root, N);
    return 0;
}