从层序构造 BST（BFS 序）

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在这里并不重要。我只是将它添加到 "catch" 第一个节点，它是我应该 return 构建的树的根。问题是我只得到根和它的 child.

如何编写这个程序？

Answer 1

你试试下面的代码怎么样？（注意：我没有测试它，因为你没有提供 class 定义。但它应该会把你推向正确的方向。）

我对 TreeNode class 的假设是它的构造函数接受一个整数并且它初始化 left 和 right 指向 null 的指针.例如：

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

从层序构造 BST（BFS 序）

Construct a BST from level order (BFS order)

java

breadth-first-search

binary-search-tree