使用PreOrder和InOrder恢復二叉樹 - Javascript

有人可以教我如何使用Prorder和Inorder數組恢復二叉樹。我已經看到了一些例子（JavaScript中沒有），它們是有道理的，但是當我嘗試寫入時遞歸調用從不返回完整的樹。也很想看到解釋。下面是一些代碼來開始：使用PreOrder和InOrder恢復二叉樹 - Javascript

創建樹節點使用此：

function Tree(x) { 
    this.value = x; 
    this.left = null; 
    this.right = null; 
}

創建樹使用這樣的：

function retoreBinaryTree(inorder, preorder) { 

}

一些樣本輸入：

inorder = [4,2,1,5,3] 
preorder = [1,2,4,3,5,6] 

inorder = [4,11,8,7,9,2,1,5,3,6] 
preorder = [1,2,4,11,7,8,9,3,5,6]

編輯我一直在這個工作了幾天，無法啓動w由於我自己的解決方案，所以我搜索了一些（大部分是用Java編寫的）。我試圖模仿this solution，但無濟於事。

來源

2017-07-30 Stephen Agwu

不錯，你嘗試過什麼？ –

我試圖創建一個名爲構建樹的遞歸函數，它接受了前序和inorder列表以及代表像start和end這樣的數字的變量。該函數將創建一個節點，根據該節點的值的索引調整開始和結束。如果它們存在，找到左右節點，然後返回節點。問題是它永遠不會返回完整的樹。在這裏，我會發布我的解決方案。 –

這是C++中的解決方案，我認爲你可以沒有問題翻譯：

/* keys are between l_p and r_p in the preorder array 

    keys are between l_i and r_i in the inorder array 
*/ 
Node * build_tree(int preorder[], long l_p, long r_p, 
      int inorder[], long l_i, long r_i) 
{ 
    if (l_p > r_p) 
    return nullptr; // arrays sections are empty 

    Node * root = new Node(preorder[l_p]); // root is first key in preorder 
    if (r_p == l_p) 
    return root; // the array section has only a node 

    // search in the inorder array the position of the root 
    int i = 0; 
    for (int j = l_i; j <= r_i; ++j) 
    if (inorder[j] == preorder[l_p]) 
     { 
     i = j - l_i; 
     break; 
     } 

    root->left = build_tree(preorder, l_p + 1, l_p + i, 
       inorder, l_i, l_i + (i - 1)); 
    root->right = build_tree(preorder, l_p + i + 1, r_p, 
       inorder, l_i + i + 1, r_i); 

    return root; 
}

來源

2017-07-30 22:49:48 lrleon

使用PreOrder和InOrder恢復二叉樹 - Javascript

回答

相關問題