从零开始刷算法——二叉树篇：层序遍历 + 有序数组转二叉搜索树
在二叉树的算法体系中，"读取"（遍历）与"写入"（构建）是两个最核心的命题。
本文将通过两道经典题目——二叉树的层序遍历与有序数组转搜索树，深入剖析两种截然不同的思维模式：基于队列的迭代（BFS）与基于递归的分治（Divide & Conquer），并从内存与指针的角度分析其底层实现。
一、 读取的艺术：二叉树的层序遍历
二叉树的层序遍历（Level Order Traversal）本质上是图论中的广度优先搜索（BFS）。不同于前中后序遍历“一条道走到黑”的深度优先逻辑，层序遍历要求我们按照“剥洋葱”的方式，一层一层地访问节点。
1. 核心代码实现
C++代码实现：
class Solution { // 思路： 先加入root进q，然后每次处理完front（）之后把它左右子树加入进去，最重要的其实还是要记录当前的size，来记录有几个数进入vals作为一组 public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> ans; if (root == nullptr) return ans; queue<TreeNode*> q; q.push(root); while (!q.empty()) { vector<int> vals; // 快照，核心逻辑：固定住当前层的 size for (int i = q.size(); i > 0; --i) { vals.push_back(q.front()->val); if (q.front()->left) q.push(q.front()->left); if (q.front()->right) q.push(q.front()->right); q.pop(); // 要不就提前用node记录下来front要不就最后pop } ans.push_back(vals); } return ans; } };2. 深度解析：队列与快照机制
很多初学者容易写成普通的 BFS，却无法将结果按层分开。上述代码中最精髓的一行在于：
for (int i = q.size(); i > 0; --i)
这里隐藏了一个**“快照”**思想：
锁定状态：在进入
for循环之前，q.size()代表了当前这一层所有的节点数量。我们必须在循环开始前就确定循环次数。动态入队：在循环内部，我们不断地
push下一层的节点（左右孩子）。时空隔离：如果不固定
i的次数，而是每次判断q.size()，那么新加入的下一层节点会和当前层混在一起，导致分层逻辑失效。
通过这个机制，队列q充当了一个缓冲区，完美地衔接了上一层的消耗和下一层的生产。
3. 时空复杂度分析
时间复杂度：O(N)
每个节点进队一次、出队一次，操作次数与节点总数 N 成正比。
空间复杂度：O(W)
W 为二叉树的最大宽度。
在最坏情况下（满二叉树的最底层），队列中需要同时存储大约 N/2 个节点，因此空间复杂度与宽度相关，数量级上视为 O(N)。
二、 构建的艺术：有序数组转二叉搜索树
如果说层序遍历是利用队列进行“横向扫描”，那么构建平衡二叉搜索树（BST）则是利用递归进行“纵向切分”。
题目要求构建高度平衡的 BST，且输入数组是有序的。这天然符合二分法和分治思想。
1. 核心代码实现
C++代码实现：
class Solution { // 思路： 题目要求平衡也就是左右高度差为1以内， 那肯定要涉及到中间点， 利用二分的思想构造子树， dfs递归构造， 因为是左小右大， 所以构造左边从mid左边选，右边从mid右边选 TreeNode* dfs(vector<int>& nums, int left, int right) { if (left > right) return nullptr; int mid = left + (right - left) / 2; TreeNode* root = new TreeNode(nums[mid]); root->left = dfs(nums, left, mid - 1); root->right = dfs(nums, mid + 1, right); return root; } public: TreeNode* sortedArrayToBST(vector<int>& nums) { return dfs(nums, 0, nums.size() - 1); } };2. 深度解析：堆内存与指针构建
在这段简短的递归代码中，TreeNode* root = new TreeNode(nums[mid]);这行代码极其关键，它揭示了 C++ 中二叉树构建的内存模型：
堆区（Heap）分配：
使用了
new关键字。这意味着节点对象是创建在堆内存中的。这一点至关重要。如果是栈上分配（例如
TreeNode node;），函数dfs一结束，节点就会被销毁。而堆上分配的节点生命周期独立于函数调用，保证了整棵树在递归结束后依然存在。
栈区（Stack）链接：
dfs函数的每一次调用都在系统栈中开辟了一个栈帧。变量
root是一个指针，暂存在栈上。root->left = dfs(...)这一步，实际上是利用栈上的递归回溯，将分散在堆内存中的各个节点，通过指针像“锁链”一样串联起来，形成了树的结构。
这种**“取中点 -> 建根 -> 递归构建左右”的顺序，本质上是二叉树的前序遍历**逻辑。
3. 时空复杂度分析
时间复杂度：O(N)
每个数组元素只会被访问一次用来创建一个节点，不存在重复计算。
空间复杂度：O(log N)
这里的空间消耗主要来自递归调用栈。
由于我们每次都取中间点（
mid），保证了生成的树是高度平衡的。平衡二叉树的高度是
log N，因此递归的最大深度也就是log N。注：这里未计算存储结果所需的 O(N) 空间，仅计算算法辅助空间。
三、 总结
这两道题目展示了二叉树算法的两种极端：
层序遍历：
数据结构：队列 (Queue)
特性：FIFO (先进先出)
思维：迭代，水平扩展，通过 size控制层级。
平衡构建：
数据结构：系统栈 (System Stack / Recursion)
特性：LIFO (后进先出)
思维：递归，深度优先，通过二分保证平衡。