从给定的级别顺序遍历构造BST


难度级别 易得奖学金
经常问 亚马逊 Apple GE医疗集团 大都会人寿 微软 UHG Optum 狗吠声
二进制搜索树 二叉树 广度优先搜索 树遍历

鉴于 级别顺序遍历 二进制搜索树的代码,编写一种算法,以从ITS给定的级别顺序遍历构造二进制搜索树或BST。

使用案列

输入
levelOrder [] = {18、12、20、8、15、25、5、9、22、31}
输出

从给定的级别顺序遍历构造BST

有序:5 8 9 12 15 18 20 22 25 31

输入
levelOrder [] = {4,2,5,1,3,6,XNUMX}
输出

从给定的级别顺序遍历构造BST

按顺序:1 2 3 4 5 6

从层级顺序遍历构造BST的算法

层级顺序遍历中的第一个元素始终构成二进制搜索的根 。 下一个值可以根据其值形成左节点或右节点。

如果下一个节点小于根节点,则将其插入根节点的左侧,否则将其插入右侧。
想法如下,如果BST的根为空,则当前元素小于根,然后将其插入到根的左子树中的适当位置,否则将其插入不适当的位置到右子树中根。

  1. 将BST的根初始化为null。 如果级别顺序遍历中没有元素,请返回root。
  2. 对于levelOrder数组中的每个元素,重复步骤3、4和5。
  3. 如果根为空,则以当前元素为根。
  4. 否则,如果当前元素小于根,请转到步骤3,根变为root.left,并且元素保持不变。
  5. 否则,如果当前元素大于根,请转到步骤3,根将变为root.right并且该元素保持不变。
  6. 返回根。

JAVA代码,用于根据级别顺序遍历构造BST

public class ConstructBSTFromItsGivenLevelOrderTraversal {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    // function to print in order traversal of a binary tree
    private static void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }

    private static Node attachNode(Node root, int value) {
        // if root is null, make the current element as root
        if (root == null) {
            root = new Node(value);
            return root;
        }

        // if element is less than root
        if (value < root.data) {
            // attach it to left subtree
            root.left = attachNode(root.left, value);
        } else {
            // attach it to right subtree
            root.right = attachNode(root.right, value);
        }

        // return root
        return root;
    }

    private static Node formBST(int[] levelOrder) {
        // initialize root as null
        Node root = null;

        // for each element attach the node to required position in the BST
        for (int i = 0; i < levelOrder.length; i++) {
            // Step 3 to 5
            root = attachNode(root, levelOrder[i]);
        }

        // return root
        return root;
    }

    public static void main(String[] args) {
        // Example 1
        int levelOrder1[] = new int[] {18, 12, 20, 8, 15, 25, 5, 9, 22, 31};
        Node root1 = formBST(levelOrder1);
        inorder(root1);
        System.out.println();

        // Example 2
        int levelOrder2[] = new int[] {4, 2, 5, 1, 3, 6};
        Node root2 = formBST(levelOrder2);
        inorder(root2);
        System.out.println();
    }
}
5 8 9 12 15 18 20 22 25 31 
1 2 3 4 5 6

从级别顺序遍历构造BST的C ++代码

#include <iostream> 
#include<vector> 
#include<queue> 
using namespace std; 

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
}; 

// function to print the in-order traversal of a binary tree 
void inOrder(Node *root) { 
    if (root != NULL) { 
        inOrder(root->left); 
        cout<<root->data<<" "; 
        inOrder(root->right); 
    } 
} 

Node* attachNode(Node *root, int value) {
    // if root is null, make the current element as root
    if (root == NULL) {
        root = new Node(value);
        return root;
    }
    
    // if element is less than root
    if (value < root->data) {
        // attach it to left subtree
        root->left = attachNode(root->left, value);
    } else {
        // attach it to right subtree
        root->right = attachNode(root->right, value);
    }
    
    // return root
    return root;
}

Node* formBST(int *levelOrder, int n) {
    // initialize root as null
    Node *root = NULL;
    
    // for each element attach the node to required position in the BST
    for (int i = 0; i < n; i++) {
        // Step 3 to 5
        root = attachNode(root, levelOrder[i]);
    }
    
    // return root
    return root;
}

int main() { 
    // Example 1
    int levelOrder1[] = {18, 12, 20, 8, 15, 25, 5, 9, 22, 31};
    Node *root1 = formBST(levelOrder1, sizeof(levelOrder1) / sizeof(levelOrder1[0]));
    inOrder(root1);
    cout<<endl;

    // Example 2
    int levelOrder2[] = {4, 2, 5, 1, 3, 6};
    Node *root2 = formBST(levelOrder2, sizeof(levelOrder2) / sizeof(levelOrder2[0]));
    inOrder(root2);
    cout<<endl;
    
    return 0; 
}
5 8 9 12 15 18 20 22 25 31 
1 2 3 4 5 6

复杂度分析

时间复杂度= 2)
空间复杂度= O(N),由于递归
其中n是按级别顺序排列的元素总数 排列.

编号1     参考2