1

我有这段代码用于从预排序遍历元素的扁平列表中重建二叉搜索树。

我看到这段代码工作，但无法理解如何。这是代码：

public static Node reconstructfromflattenBST(List<Integer> list){
        if (list.isEmpty()){
            return null;
        }
        int data = list.remove(0);
        Node root = new Node(data);
        root.left=reconstructfromflattenBST(list);
        root.right=reconstructfromflattenBST(list);

        return root;



    }

根据我对这种方法的理解，不会创建正确的树。因为当控制到达时root.right，list是空的。但这种方法显然有效。

我给出了 [5 3 1 4 8 6 9] 的预购输入。构建树后，我对构建的树进行了前序遍历，它给出了与输入列表相同的元素顺序。

编辑：这是我的展平子程序：

public static List<Integer> flattenBinaryTree(Node root, List<Integer> list){

        if (list==null){
            list=new ArrayList<Integer>();
        }
        if (root==null){
            return list;
        }
        list.add(root.data);
        List<Integer> list1 = flattenBinaryTree(root.left,list);
        return flattenBinaryTree(root.right, list1);
    }
4

3 回答 3

1

你说的对。如果在展平树时空节点也被写出，可能是空整数，那么：

    Integer data = list.remove(0);
    if (data == null) {
        return null;
    }
    Node root = new Node(data.intValue());

将重建完全相同的树。即：展平添加了停止的空叶。

List<Integer> list = new LinkedList<>();
flatten(list, tree);

void flatten(List<Integer> list, Node tree) {
    if (tree == null) {
        list.add(null);
        return;
    }
    list.add(tree.data);
    flatten(tree.left);
    flatten(tree.right);
}

或使用有序树：

public static Node reconstructfromflattenBST(List<Integer> list){
    reconstruct(list, Integer.MAX_VALUE, true);
}

public static Node reconstruct(List<Integer> list, int priorData, boolean left){
    if (list.isEmpty()){
        return null;
    }
    int data = list.remove(0);
    if ((data <= priorData) != left) {
        return null;
    }
    Node root = new Node(data);
    root.left=reconstruct(list, data, true);
    root.right=reconstruct(list, data, false);

    return root;
}
于 2014-01-14T20:10:58.873 回答
1

根据我对这种方法的理解，不会创建正确的树。因为当控制到达时root.right，list是空的。

这是正确的。

但这种方法显然有效。

我给出了 [5 3 1 4 8 6 9] 的预购输入。构建树后，我对构建的树进行了前序遍历，它给出了与输入列表相同的元素顺序。

这种观察与右子树总是空的并不矛盾。

更好的单元测试将构建一棵树，将其展平，重构它，并比较重构的树与原始树的形状相同。这样的测试会失败。事实上，从节点的预排序列表中忠实地重建树是不可能的，因为不同的树具有相同的预排序列表。例如，两者

1              1
 \            / \
  2          2   3
   \
    3

有预购清单 1 2 3。

于 2014-01-14T21:22:34.943 回答
0

我认为问题在于写出树的预序值并不能保证树最初是 BST，因此初始函数的输出应该是一根从左侧向下的棒，以 5 为根。

      5
     3
    1
   4
  8
 6
9

这棵树具有 [5, 3, 1, 4, 8, 6, 9] 的前序遍历，但是它不是 BST，因此不是树的正确表示。Joop Eggen 出现了正确的版本

于 2014-01-14T21:59:03.987 回答