java - 从Java中的展平列表重建二叉搜索树？

Question

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

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

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);
    }

Answer 1

你是对的。如果在展平树时 null 节点也被写出，可能作为 null Integer，那么:

    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;
}