從給定的預先遍歷構建二叉樹

Question

我有一個存儲在數組中的二叉樹的預遍歷，我想重新創建基於此遍歷的二叉樹。我的數組看起來像這樣：{NNNLLNLLNLNLNNLLNLL}，其中N代表節點，L代表葉。我想遞歸地做到這一點，但我有麻煩提出一個算法。任何建議將非常感激。

Answer 1

在重建樹之前，您還需要再進行一次遍歷。鑑於三個（Pre，Post，In）之間的任何兩次遍歷，您可以重建。但只有一個，不可能唯一地重構樹。

Answer 2

這應該假設每個節點都有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