java - 从层序(BFS 序)构建 BST

Question

我尝试根据给定的级别顺序(BFS 顺序)构造 BST。我知道这是可能的，但我不知道我该怎么写。问题是我必须使用 BFS 序列。所以，我不能在这里使用递归，我必须迭代地编写我的程序......我发现这有点令人困惑。

我尝试这样做:

public static TreeNode constructBFSTree(ArrayList<Integer> bfs) {
    if (bfs== null) return null;
    ArrayList<TreeNode> result = new ArrayList<TreeNode>();
        for (int i = 0; i < bfs.size()-1; i ++){
             TreeNode node = result.get(i);
             int leftValue = (bfs.get(i+1)!=null)? bfs.get(i+1) : Integer.MAX_VALUE ;
             int rightValue = (bfs.get(i+2)!=null)? bfs.get(i+2) : Integer.MIN_VALUE;

             node.left = (leftValue <= node.data)? new TreeNode(leftValue) : null;
             node.right = (rightValue > node.data)? new TreeNode(rightValue) : null;
             result.add(node);
        }

        return result.get(0);
    }

本地 ArrayList 在这里并不重要。我只是将它添加到“捕获”第一个节点，该节点是我应该返回的构造树的根。问题是我只能得到根及其子项。

如何编写这个程序？

Answer 1

你试试下面的代码怎么样？ (注意:我没有测试它，因为您没有提供类定义。但它应该会插入您走向正确的方向。)

我对 TreeNode 类的假设是，它的构造函数采用一个整数，并将 left 和 right 指针初始化为 空。例如:

class TreeNode {
    TreeNode left;
    TreeNode right;
    int key;
    public TreeNode(int key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
}

该函数的代码如下:

public static TreeNode constructBFSTree(ArrayList<Integer> bfs) {
    if (bfs == null || bfs.isEmpty()) {
        return null;
    }

    Queue<TreeNode> q = new Queue<TreeNode>();
    TreeNode root = new TreeNode(bfs.get(0));
    q.add(root);
    int i = 1;
    while (!q.isEmpty() && i < bfs.size()) {
        TreeNode currentNode = q.poll();
        currentNode.left = new TreeNode(bfs.get(i++));
        q.add(curentNode.left);
        if (i < bfs.length()) {
            currentNode.right = new TreeNode(bfs.get(i++));
            q.add(currentNode.right);
        }
    }
    return root;
}