java - 从遍历构建二叉树

Question

鉴于其遍历，我正在尝试构造一棵二叉树(不平衡)。我目前正在做预购+中序，但当我发现后序将完全没有问题。

我意识到已经有一些关于该主题的问题，但他们似乎都没有回答我的问题。我有一个递归方法，它采用二叉树的预序和中序来重建它，但由于某种原因无法将根节点与后续子节点链接起来。

注意:我不需要解决方案。我已经尝试解决这个问题几个小时了，甚至在纸上记下了递归，一切看起来都很好......所以我一定错过了一些微妙的东西。代码如下:

    public static <T> BinaryNode<T> prePlusIn( T[] pre, T[] in)
{
    if(pre.length != in.length)
        throw new IllegalArgumentException();

    BinaryNode<T> base = new BinaryNode();
    base.element = pre[0]; // * Get root from the preorder traversal.
    int indexOfRoot = -1 ;

    if(pre.length == 0 && in.length == 0)
        return null;

    if(pre.length == 1 && in.length == 1 && pre[0].equals(in[0]))
        return base; // * If both arrays are of size 1, element is a leaf.

    for(int i = 0; i < in.length -1; i++){
        if(in[i].equals(pre[0])){    // * Get the index of the root
            indexOfRoot = i; // in the inorder traversal.
            break;
        } 

    }   // * If we cannot, the tree cannot be constructed as the traversals differ.

        if (indexOfRoot == -1) throw new IllegalArgumentException();

    // * Now, we recursively set the left and right subtrees of 
    // the above "base" root node to whatever the new preorder
    // and inorder traversals end up constructing.

    T[] preleft = Arrays.copyOfRange(pre, 1, indexOfRoot + 1);
    T[] preright = Arrays.copyOfRange(pre, indexOfRoot + 1, pre.length);
    T[] inleft = Arrays.copyOfRange(in, 0, indexOfRoot);
    T[] inright = Arrays.copyOfRange(in, indexOfRoot + 1, in.length);

    base.left = prePlusIn( preleft, inleft); // * Construct left subtree.
    base.right = prePlusIn( preright, inright); // * Construc right subtree.

    return base; // * Return fully constructed tree
}

基本上，我构造了额外的数组来容纳左子树和右子树的预遍历和中序遍历(这看起来效率非常低，但我想不出没有辅助方法的更好方法)。

任何想法将不胜感激。

旁注:在调试时，根注释似乎从未收到与其他节点的连接(它们保持为空)。但据我所知，这不应该发生......

编辑:澄清一下，该方法在第 21 行抛出 IllegalArgumentException (for 循环的 else 分支，它应该only如果遍历包含不同元素，则抛出该异常。

EDIT2:感谢 @Philip 的一篇有用的帖子(巧合的是，我们有相同的名字......有趣!)。但是，如果有人对提高效率有任何建议，我将不胜感激。

Answer 1

这段代码对我来说非常可疑

for(int i = 0; i < in.length -1; i++){
    if(in[i].equals(base.element)){    // * Get the index of the root
        indexOfRoot = i; // in the inorder traversal.
        break;
    } // * If we cannot, the tree cannot be constructed as the traversals differ.
    else throw new IllegalArgumentException();
}

您进入循环并 i设置为 0，如果 i小于in.length - 1您评估循环体，它是一个 if 表达式。此时将发生以下两种情况之一

1. in[i]等于 base.element在这种情况下indexOfRoot将被设置为 0 并且您将跳出循环
2. 您抛出异常

无论哪种方式，你都不会真正增加 i

尝试重新设计此循环以执行您想要的操作，因为它现在肯定没有执行您想要的操作。你可以尝试类似的事情

int indexOfRoot = -1; //an impossible value
for(int i = 0; i < in.length -1; i++){
    if(in[i].equals(base.element)){    // * Get the index of the root
        indexOfRoot = i; // in the inorder traversal.
        break;
    } 
} 
if(indexOfRoot == -1){//if the root was never set
    throw new IllegalArgumentException();
}

尽管这仍然有点难看(一方面， base.element 永远不会改变，所以为了清楚起见，您可能需要使用 pre[0] )。而且，我绝不确定它是完全正确的。尽管如此，它可能更接近你想要的