使用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

回答

相关问题