java - 用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. if (preorder[i]== postorder[lowIndex]) 行有两个错误:第一个是您按前序而不是后序搜索，第二个是您使用 lowIndex 代替前索引。 这一行应该是: if (preorder[index.index]== postorder[i])
2. 行 TreeNode root = new TreeNode (preorder[lowIndex]); - 再次使用 lowIndex 而不是 preIndex。 这一行应该是: TreeNode root = new TreeNode (preorder[index.index]);

请注意，此代码仅适用于完整二叉树