- 正确答案：实现一个完整的程序，从输入的层序遍历序列（如用数组表示）构建二叉树，并输出该二叉树的左视图。左视图是指从左侧看过去每一层最左边可见的节点值，按层顺序输出。例如输入：[1,2,3,null,5,null,4] 输出左视图应为：[1,2,5] - 解答思路： 1. 首先需要根据给定的层序遍历序列（包括 null 表示空节点）重建二叉树结构。 2. 然后使用层序遍历（BFS）或深度优先搜索（DFS）来获取每层最左侧的节点。 - 使用 BFS 时，在每一层的第一个非空节点加入结果即可。 - 使用 DFS 时，优先访问左子树，记录当前深度第一次访问的节点。 3. 输出左视图的结果列表。本题是 LeetCode 199 “二叉树的右视图” 的改编版，将“右视图”改为“左视图”，核心逻辑类似，但取的是每层第一个节点而非最后一个。 - 深度知识讲解： 1. **二叉树的层序序列化与反序列化**：在 ACM 或笔试模式中，通常不会直接给出树结构，而是以数组形式给出层序遍历结果（如 [1,2,3,null,5,null,4]），需要手动建树。建树方法： - 使用队列进行广度优先构造。 - 将数组元素依次取出，用一个指针 index 遍历数组。 - 根节点入队，然后每次出队一个非空节点，为其分配左右孩子（如果对应位置不是 null），并将非空孩子重新入队。 2. **数据结构定义**：二叉树节点结构体如下： ``` struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; ``` 3. **左视图算法选择**： - 方法一：BFS（推荐）层序遍历每一层，记录每层第一个节点。时间复杂度 O(n)，空间复杂度 O(w)，w 是最大宽度。 - 方法二：DFS 使用递归，维护一个 depth 记录当前层数，以及一个结果数组 res。每次先访问左子树，当 depth == res.size() 时说明这是该层第一次访问，加入当前节点值。因为先左后右，所以每层最先访问的就是最左边的节点。 4. **关键点对比右视图**： - 右视图：每层最后一个节点 → BFS 中取每层末尾；DFS 先右再左。 - 左视图：每层第一个节点 → BFS 中取每层开头；DFS 先左再右。 - 扩展知识点： - 完全二叉树的数组表示法：索引 i 的左孩子为 2*i+1，右孩子为 2*i+2。 - 但本题输入可能是普通二叉树含 null，不能直接用数组下标跳转，必须模拟队列建树。 - null 的处理：在 C++ 中可用特殊标记（如 INT_MIN）或字符串 "null" 输入解析；在代码中判断是否为空。 - 完整可运行代码（C++ ACM 模式风格）： ``` #include #include #include using namespace std; // 二叉树节点定义 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // 从层序遍历数组构建二叉树 TreeNode* buildTree(vector& arr) { if (arr.empty() || arr[0] == -1) return nullptr; // 假设 -1 表示 null TreeNode* root = new TreeNode(arr[0]); queue q; q.push(root); int i = 1; while (!q.empty() && i < arr.size()) { TreeNode* node = q.front(); q.pop(); // 构建左子树 if (i < arr.size() && arr[i] != -1) { node->left = new TreeNode(arr[i]); q.push(node->left); } i++; // 构建右子树 if (i < arr.size() && arr[i] != -1) { node->right = new TreeNode(arr[i]); q.push(node->right); } i++; } return root; } // 方法一：BFS 获取左视图 vector leftView(TreeNode* root) { vector result; if (!root) return result; queue q; q.push(root); while (!q.empty()) { int levelSize = q.size(); // 当前层的节点数 // 遍历当前层的所有节点 for (int i = 0; i < levelSize; ++i) { TreeNode* node = q.front(); q.pop(); // 第一个节点就是最左边的节点 if (i == 0) { result.push_back(node->val); } // 加入下一层节点 if (node->left) q.push(node->left); if (node->right) q.push(node->right); } } return result; } // 方法二：DFS 获取左视图（辅助函数） void dfsLeftView(TreeNode* node, int depth, vector& res) { if (!node) return; // 如果当前深度等于结果长度，说明是这一层第一次访问 if (depth == res.size()) { res.push_back(node->val); } // 先递归左子树，再右子树，保证每层最左节点先被访问 dfsLeftView(node->left, depth + 1, res); dfsLeftView(node->right, depth + 1, res); } // 主函数 int main() { // 输入样例：[1,2,3,-1,5,-1,4] 其中 -1 表示 null vector input = {1, 2, 3, -1, 5, -1, 4}; // 对应层序遍历 TreeNode* root = buildTree(input); // 方法一：BFS 得到左视图 vector view = leftView(root); // 输出结果 cout << "左视图为: "; for (int val : view) { cout << val << " "; } cout << endl; // 方法二：验证 DFS 方法 vector dfsRes; dfsLeftView(root, 0, dfsRes); cout << "DFS左视图: "; for (int val : dfsRes) { cout << val << " "; } cout << endl; return 0; } ``` - 运行说明： - 输入数组中使用 -1 表示 null 节点。 - buildTree 函数通过队列逐层恢复树结构。 - BFS 方法更直观，适合面试手撕。 - DFS 方法节省空间且只需一次遍历，但需理解递归深度控制。 - 易错点提醒： 1. 建树时忘记判断 arr[i] 是否为 -1（null），导致创建非法节点。 2. 忘记 i++ 导致重复读取或死循环。 3. BFS 中未正确区分层边界（要用 levelSize 控制）。 4. DFS 中访问顺序写成先右后左，则变成右视图逻辑。 - 总结：此题综合考察： - 二叉树的重建（序列化/反序列化） - 层序遍历与队列应用 - 深度优先搜索中的状态记录 - 边界条件处理能力建议掌握两种方法，手撕时优先写 BFS 版本，清晰不易出错。

字节推荐算法面经

全站热榜

创作者周榜