c++ - 从给定的前序遍历构建二叉树

Question

我有一个存储在数组中的二叉树的前序遍历，我想根据这个遍历重新创建二叉树。我的数组如下所示：{NNNLLNLLNLNLNNLLNLL}，其中 N 代表一个节点，L 代表一个叶子。我想以递归方式执行此操作，但在提出算法时遇到了麻烦。任何建议将不胜感激。

Answer 1

假设每个节点都有 2 或 0 个后代，这应该可以工作（满足此属性的树称为完整或严格二叉树）

void create_from_traversal(Node* root, int& index) {
    if (traversal[index] == 'L') {
        root->left = root->right = NULL;
        return;
    }
    root->left = new Node();
    create_from_traversal(root->left, ++index);
    root->right = new Node();
    create_from_traversal(root->right, ++index);
}

带检查的完整示例：

#include <string>
#include <iostream>

class Node {
public:
    Node* left;
    Node* right;
};

std::string traversal = "NNNLLNLLNLNLNNLLNLL";

void create_from_traversal(Node* root, int& index) {
    if (traversal[index] == 'L') {
        root->left = root->right = NULL;
        return;
    }
    root->left = new Node();
    create_from_traversal(root->left, ++index);
    root->right = new Node();
    create_from_traversal(root->right, ++index);
}

void print_traversal(Node* root) {
    if (root->left == NULL) {
        std::cout << "L";
        return;
    }
    std::cout << "N";
    print_traversal(root->left);
    print_traversal(root->right);
}

int main() {
    Node* root = new Node();
    int index = 0;
    create_from_traversal(root, index);

    // Does it work?
    print_traversal(root); // Output should be equal to given traversal
    std::cout << std::endl;
}

输出：

NNNLLNLLNLNLNNLLNLL

Answer 2

在重建树之前，您需要再遍历一次。给定三个（Pre，Post，In）中的任意两个遍历，您可以重建。但是仅给定一个，就不可能唯一地重建树。