用Java重写C代码以构造完整的二叉树

Question

我想编写一个函数来构造一个给定前序和后序数组的完整二叉树.我找到了链接http://www.geeksforgeeks.org/full-and-complete-binary-tree-from-given-preorder-and-postorder-traversals/,它提出了以下C代码:

 struct node* constructTreeUtil (int pre[], int post[], int* preIndex,
                            int l, int h, int size)
{
// Base case
if (*preIndex >= size || l > h)
    return NULL;

// The first node in preorder traversal is root. So take the node at
// preIndex from preorder and make it root, and increment preIndex
struct node* root = newNode ( pre[*preIndex] );
++*preIndex;

// If the current subarry has only one element, no need to recur
if (l == h)
    return root;

// Search the next element of pre[] in post[]
int i;
for (i = l; i <= h; ++i)
    if (pre[*preIndex] == post[i])
        break;

// Use the index of element found in postorder to divide postorder array in
// two parts. Left subtree and right subtree
if (i <= h)
{
    root->left = constructTreeUtil (pre, post, preIndex, l, i, size);
    root->right = constructTreeUtil (pre, post, preIndex, i + 1, h, size);
}

return root;
}

 // The main function to construct Full Binary Tree from given preorder and 
// postorder traversals. This function mainly uses constructTreeUtil()
struct node *constructTree (int pre[], int post[], int size)
{
int preIndex = 0;
return constructTreeUtil (pre, post, &preIndex, 0, size - 1, size);
}

我试图用Java重写这段代码.这是我的代码:

private static TreeNode constructTree(int[] preorder, int[] postorder, Index index, int lowIndex, int highIndex){

    // Base case
    if (index.index >= preorder.length || lowIndex > highIndex){
        return null;
    }

      // The first node in preorder traversal is root. So take the node at
      // preIndex from preorder and make it root, and increment preIndex
    TreeNode root = new TreeNode (preorder[lowIndex]);
    index.index++;

      // If the current subarry has only one element, no need to recur
    if (lowIndex == highIndex){
        return root;
    }

      // Search the next element of pre[] in post[]
    int i = 0;
    for (i = lowIndex; i <= highIndex; ++i)
        if (preorder[i]== postorder[lowIndex])
            break;

    // Use the index of element found in postorder to divide postorder array in
    // two parts. Left subtree and right subtree
        if (i <= highIndex) {
            root.left = constructTree(preorder, postorder, index, lowIndex, i);
            root.right = constructTree(preorder, postorder, index, i + 1, highIndex);
        }
        return root;
                    }

    //The main function to construct Full Binary Tree from given preorder and 
    //postorder traversals. This function mainly uses constructTreeUtil()
public static TreeNode constructTree (int preorder[], int postorder[]) {
    return constructTree (preorder, postorder, new Index(), 0, preorder.length - 1);
   }

但是我在根节点中得到了一个连续的循环(它没有传递给必须是它的子节点的其他节点).你能帮我看看我的Java代码中的错误在哪里？

我不是很确定,但我认为错误可能来自这些方面:

    int i = 0;
    for (i = lowIndex; i <= highIndex; ++i)
        if (preorder[i]== postorder[lowIndex])
            break;

我不太了解原始C代码中的对应行.特别是在这一部分

Answer 1

以下是错误:

1. Line if (preorder[i]== postorder[lowIndex])有两个错误:第一个是您在预订中而不是在后序中搜索,第二个是您使用lowIndex而不是preIndex. 这一行应该是: if (preorder[index.index]== postorder[i])
2. Line TreeNode root = new TreeNode (preorder[lowIndex]);- lowIndex再次使用而不是preIndex. 这一行应该是: TreeNode root = new TreeNode (preorder[index.index]);

请注意此代码仅适用于完整二叉树的事实