在Java中重写一段C代码构造满二叉树

Question

我想编写一个函数来根据给定的前序和后序数组构造完整的二叉树。我发现 link 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

假设你用 C 编写的代码可以工作，那么我的猜测是这部分

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

您希望使用在 C 版本中使用的相同变量。在这种情况下，您的 if 语句应该是

if (preorder[index.index]== postorder[i])

Answer 2

错误如下：

行if (preorder[i]== postorder[lowIndex])有两个错误：第一个是你按前序而不是后序搜索，第二个是你使用lowIndex而不是preIndex。 这一行应该是： if (preorder[index.index]== postorder[i])
第 TreeNode root = new TreeNode (preorder[lowIndex]); 行 - 再次使用 lowIndex 而不是 preIndex。 这一行应该是： TreeNode root = new TreeNode (preorder[index.index]);

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

Answer 3

首先将您的 TreeNode 变成 class，因为它是 java 等同于结构

public class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val){
        this.val = val;
    }
}

然后制作你的 TreeUtil class

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

        // Base case
        if (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[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[]
        for (int i = lowIndex; i <= highIndex; i++)
            if (preorder[index]== postorder[i]){
                // Use the index of element found in postorder to divide postorder array in
                // two parts. Left subtree and right subtree
                root.left = constructTree(preorder, postorder, index, lowIndex, i);
                root.right = constructTree(preorder, postorder, index, i + 1, highIndex);
                break;
            }
        }
        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, 0, 0, preorder.length - 1);
    }
}

如 aviad 所述，您的代码中的错误是 if (preorder[i]== postorder[lowIndex] 和 TreeNode root = new TreeNode (preorder[lowIndex]);。我更改了您的代码，以减少您的困惑。使用索引是一种迷惑自己的好方法，尤其是因为 int 可以正常工作。另外 ++i 在运行循环之前递增并且通常不在 java 中使用，并且 java 允许您将变量声明为循环定义的一部分，所以我将 for 循环更改为更多您想要的。

在Java中重写一段C代码构造满二叉树

Rewrite a C code in Java to construct full binary tree

java

binary-tree