经典面试题目：二叉树遍历

一、核心定义与性质

二叉树（Binary Tree） 是一种每个节点最多有两个子节点的树形结构。这两个子节点通常被称为左子节点和右子节点。

关键术语：

不同类型的二叉树具有不同的性质和性能表现，这是测试时需要重点关注的。

类型	描述	测试关注点
满二叉树（Full Binary Tree）	每个节点都有0个或2个子节点。	结构完整性测试。
完全二叉树（Complete Binary Tree）	除最后一层外，所有层都完全填满，且最后一层的节点都向左对齐。	高效数组存储（堆结构的基础）。测试其构建和调整过程。
完美二叉树（Perfect Binary Tree）	所有叶子节点都在同一层，且每个非叶子节点都有两个子节点。	理想情况，常用于计算树的高度和节点数关系（第k层有$2^{k-1}$个节点）。
平衡二叉树（Balanced Binary Tree）	任何节点的左右两个子树的高度差绝对值不超过1（AVL树）或通过算法维持平衡（红黑树）。	核心！性能保证的关键。测试插入、删除操作后是否能通过旋转等操作重新平衡，以保证最坏情况下时间复杂度仍为`O(log n)`。
二叉搜索树（BST, Binary Search Tree）	一种有序的二叉树。对于任意节点，其左子树上所有节点的值都小于它，其右子树上所有节点的值都大于它。	核心！测试其顺序性是否在任何操作后都得以维持。测试查找、插入、删除功能。

遍历是访问树中所有节点的过程。不同的遍历顺序会产生不同的输出，这是验证树结构是否正确的重要手段。

遍历方式	访问顺序	应用场景	测试验证点
前序遍历（Pre-order）	根 -> 左 -> 右	用于复制一棵树（先复制根节点）。	验证树的结构是否与预期一致。
中序遍历（In-order）	左 -> 根 -> 右	对BST非常重要！会以升序访问所有节点。	这是测试BST是否正确实现的最重要方法。只要中序遍历结果是升序序列，就基本证明BST的顺序性质得以保持。
后序遍历（Post-order）	左 -> 右 -> 根	用于先删除子节点再删除父节点的场景（如释放内存）。	验证子树操作是否已完成。
层序遍历（Level-order）	从上到下，从左到右	按层次处理节点。	验证完全二叉树的性质，或用于寻找最短路径（如BFS）。

给定一棵二叉树的前序遍历序列和中序遍历序列，请你求出该二叉树的后序遍历序列。
输入：
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

解析：

答案：后序遍历：[9,15,7,20,3]

基础功能验证：
- 插入与查找：测试插入一系列值后，能否正确找到存在的值和不存在的值。
- 删除：覆盖三种情况：删除叶子节点、删除有一个子节点的节点、删除有两个子节点的节点。每次删除后都要验证树的结构。
- 核心验证手段：中序遍历。这是测试BST的‘银弹’。无论进行多少次插入或删除，只要中序遍历输出的序列是严格升序的，就能基本证明BST的核心性质——顺序性——没有被破坏。
边界和异常测试：
- 操作空树。
- 插入重复值（根据需求规格说明，测试是忽略、覆盖还是报错）。
- 插入极值（非常大或非常小的数字）。
- 尝试删除一个不存在的节点。
性能测试：
- 平衡性测试：构造随机数据和构造有序数据分别进行插入。对于有序数据，一个优质的BST（如AVL树、红黑树）应该通过自平衡操作保持树的大致平衡，确保查找效率维持在O(log n)。如果树退化成链表，性能会下降到O(n)，这是一个重要的测试点。
- 压力测试：插入大量数据，验证内存使用和操作耗时是否符合预期。
健壮性测试（如果适用）：
- 考虑并发环境下多个线程同时读写BST的情况，测试是否需要额外的同步机制，以及是否存在竞态条件。”

作者：AmyZYX
出处：http://www.cnblogs.com/amyzhu/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。