树的左视图

给定一个包含唯一元素的数组，构建一个二叉搜索树并打印树的左视图。树的左视图是指从树的左侧观察时可见的节点集合。

让我们举个例子来理解需要做什么。

如果树是

如果我们从左边观察这棵树，我们可以看到节点 1、2、3、4 和 5。

所以左视图是 1、2、3、4、5。

如果树是

如果我们从左边观察，我们可以看到 3、2、1，只有三个元素。

所以左视图是 3 2 1。

让我们来实现这段代码。

代码

输出

说明

1. 类定义（class node）

定义了一个名为 node 的类，代表二叉树中的一个节点。

公共成员包括指向左右子节点的指针（node* left, node* right）和一个数据成员（long long int data）。

构造函数初始化数据并将左右指针都设置为 NULL。

2. insertnode 函数

接收一个二叉搜索树（BST）的根节点和一个元素（ele）作为输入。

将具有给定元素的这个新节点插入到 BST 中。

通过将元素与当前节点的数据进行比较来递归调用自身以遍历树。

插入后返回 BST 更新后的根节点。

3. main 函数

从用户那里读取测试用例的数量（t）。

对于每个测试用例

读取二叉搜索树中的元素数量（n）。

初始化一个指向 BST 根节点的指针（node* root）为 NULL。

逐个读取元素，并使用 insertnode 函数将它们插入到 BST 中。

4. 层序遍历

使用广度优先搜索（BFS）方法对 BST 进行层序遍历。

使用一个队列（queue<node*> q）来跟踪每一层的节点。

对于每一层

从队列中弹出节点，打印每一层的第一个节点的（数据）。

将每个节点的左右子节点（如果存在）入队。

5. 输出

对于每个测试用例，根据层序遍历打印 BST 每一层第一个节点的（数据）。

让我们讨论一下代码的时间和空间复杂度

时间复杂度

insertnode 函数

向二叉搜索树中插入一个节点的平均时间复杂度为 O(log N)，其中 N 是树中的节点数。

然而，在最坏的情况下（倾斜树），时间复杂度可能为 O(N)，其中 N 是树中的节点数。

层序遍历（BFS）

层序遍历涉及访问每个节点一次。

在最坏的情况下，所有节点都会被访问，导致时间复杂度为 O(N)，其中 N 是树中的节点数。

总体时间复杂度

在最坏的情况下，整体时间复杂度由层序遍历主导：O(N)。

空间复杂度

insertnode 函数

insertnode 函数的空间复杂度平均为 O(log N)，这是由于递归调用栈。在最坏的情况下（倾斜树），空间复杂度可能为 O(N)。

层序遍历（BFS）

BFS 遍历的空间复杂度为 O(W)，其中 W 是二叉树的最大宽度（同一层的节点数）。

在最坏的情况下（完全不平衡的树），宽度 W 可能为 N，导致 O(N) 的空间复杂度。

总体空间复杂度

总体空间复杂度在最坏情况下由 BFS 遍历所需空间主导：O(N)。

总结

时间复杂度：O(N)

空间复杂度: O(N)

请注意，这些复杂度是基于最坏情况的。