java - 如何从层序数组构造二叉树？

Question

我正在解决一个编码问题，现在我有点困惑。如果给我一个表示二叉树的级别顺序遍历的数组。我如何从中构建一棵树？

到目前为止，这是我的思考过程:我知道 0th 索引是 root，leftChild = 2*i+1和rightChild = 2*i+2。

这是我到目前为止所得到的，但我认为它不正确:

public Tree buildTree(ArrayList<Tree> arr, int i) {
    if (i > list.size() - 1) {
        return null;
    }

    root = list.get(i);
    root.LeftChild = buildTree(arr, 2*i+1);
    root.RightChild = buildTree(arr, 2*i+2);

    return root;
}

我的i从0开始，谢谢。

Answer 1

您的代码仅适用于 complete binary trees ，二叉树的一种特殊情况。

您不能仅通过级别顺序遍历构建通用二叉树。

您需要两次次遍历，其中一次必须是中序遍历。

以下组合可以唯一标识一棵树。

• 有序和预序。
• 按序和后序。
• 有序和级别顺序。

尽管如果给定数组中有一些分隔符，则有可能构建树(仅给出级别顺序遍历)，如 this post 中所述。 。