算法选择题：树与二叉搜索树（5 题）

036 关于二叉树前序、中序、后序遍历，哪种表述准确？

难度： 基础

• A. 中序遍历总是输出降序序列
• B. 后序遍历必须用栈实现，递归无法实现
• C. 三种遍历只是输出位置随意调整，结果必然相同
• D. 根节点在递归处理左、右子树之前、之间、之后的相对位置决定遍历顺序；具体选择取决于任务需要根信息还是子树结果

查看答案与解析

正确答案D

正确原因： 根节点在递归处理前、中、后的相对位置决定遍历顺序；具体选择取决于任务需要根信息还是子树结果。

错误选项辨析： A 项：只有二叉搜索树的中序遍历才有序，且是升序而非降序；B 项：递归同样可以实现后序，先处理子树再处理根即可；C 项：根位置不同使三种遍历的输出序列通常不同。

037 递归 DFS 遍历二叉树，调用栈空间与什么相关？

难度： 进阶

• A. 调用栈深度与树高成正比；退化链形树的高度为 n，栈空间可达 O(n)
• B. 只有 BFS 才会占用额外空间，DFS 完全不需要
• C. 树遍历的递归栈空间恒为 O(log n)
• D. 递归不占用额外空间，栈空间恒为 O(1)

查看答案与解析

正确答案A

正确原因： 递归 DFS 的调用栈与树高成正比；退化链形树的栈空间可达到 O(n)。

错误选项辨析： B 项：递归 DFS 的调用栈本身就是额外空间；C 项：平衡树才是 O(log n)，退化链形树可达到 O(n)；D 项：递归调用栈属于额外空间，随深度增长。

038 二叉树层序遍历（BFS）的队列峰值空间由什么决定？

难度： 进阶

• A. BFS 必须把整棵树复制一份到队列
• B. BFS 空间只与树高有关，恒为 O(log n)
• C. BFS 的额外空间恒为 O(1)
• D. 队列峰值与树的最大宽度相关；平衡二叉树最后一层可能包含 O(n) 个节点

查看答案与解析

正确答案D

正确原因： 层序遍历队列峰值与树的最大宽度相关；平衡树最后一层可能包含 O(n) 个节点。

错误选项辨析： A 项：队列只需保存当前层节点，不需要复制整棵树；B 项：决定峰值的是宽度而非高度，平衡树末层宽度可达 O(n)；C 项：队列需要保存一层节点，宽度可达 O(n)。

039 验证一棵二叉树是否为二叉搜索树（BST），为什么不能只比较父节点与直接孩子？

难度： 进阶

• A. 只要根节点大于左子树根、小于右子树根即可
• B. BST 要求整棵子树都在祖先给出的上下界内；只比较父子会漏掉跨层违规，必须传递全局边界（或等价的中序严格递增）
• C. 每个节点大于左孩子且小于右孩子就足够
• D. BST 验证必须使用 BFS，递归无法实现

查看答案与解析

正确答案B

正确原因： 验证 BST 必须把祖先给出的上下界传递到整棵子树；只比较父节点与直接孩子无法发现跨层违规。

错误选项辨析： A 项：只比较子树根会漏掉深层越界节点；C 项：跨层节点可能突破祖先边界，例如右子树中的过小节点；D 项：递归传递上下界或中序遍历都可以正确验证。

040 自底向上判断二叉树是否平衡，如何把复杂度控制在 O(n)？

难度： 综合

• A. 必须为每个节点维护父指针才能判断平衡
• B. 对每个节点重复求左右子树高度，总复杂度仍是 O(n)
• C. 后序遍历一次返回子树高度，并用特殊值传播不平衡；每个节点只计算一次高度才能保持 O(n)
• D. 只要递归层数不超过 log n，树就一定是平衡的

查看答案与解析

正确答案C

正确原因： 后序一次返回子树高度并用特殊值传播不平衡；每个节点只能计算一次高度才能保持 O(n)。

错误选项辨析： A 项：后序递归不需要父指针，返回子树高度即可；B 项：每个节点都递归求高度会让总工作量退化为 O(n²)；D 项：高度限制是平衡的必要条件，递归深度本身不证明平衡。