UD5工具箱
问：什么是二叉树遍历？为什么需要不同的遍历方式？
答：二叉树遍历是指按照某种规则系统地访问树中的每个节点，且每个节点恰好被访问一次。不同的遍历方式适用于不同的应用场景：前序遍历适合复制树结构和序列化存储；中序遍历可以获得二叉搜索树的有序序列；后序遍历适合先处理子节点再处理父节点的场景（如删除树、计算目录大小）；层序遍历用于广度优先搜索和按层处理数据。理解遍历方式是数据结构与算法学习的基础。
问：前序、中序、后序遍历的核心区别是什么？
答：三种深度优先遍历的核心区别在于访问根节点的时机不同。前序遍历（Preorder）的顺序是根-左-右，首次遇到节点时就立即访问；中序遍历（Inorder）的顺序是左-根-右，从左子树返回后才访问根节点；后序遍历（Postorder）的顺序是左-右-根，处理完所有子节点后才访问根节点。层序遍历（Level-order）则完全不同，它按深度层级逐层访问，使用队列实现广度优先搜索。三种深度优先遍历都可用递归或栈实现，时间复杂度均为O(n)。
问：只用前序和中序遍历序列能否唯一确定一棵二叉树？
答：可以。已知前序加中序或后序加中序两种遍历序列都能唯一重建一棵二叉树。具体方法是：前序序列的第一个元素就是根节点，在中序序列中找到该元素的位置，其左边的部分构成左子树，右边的部分构成右子树，然后递归处理即可。但仅凭前序加后序两种序列无法唯一确定二叉树，因为无法区分左右子树的具体结构（除非树是满二叉树）。层序遍历配合中序遍历也可以重建二叉树。这是算法面试中的经典问题。
问：二叉树的数组表示法是什么？null有什么作用？
答：二叉树可以用数组按层序编号存储，根节点在索引0，节点i的左子节点在2i+1位置，右子节点在2i+2位置，父节点在向下取整((i-1)/2)位置。null表示该位置不存在实际节点，但其索引位置被保留以确保子节点与父节点的索引关系正确。例如数组[1,2,3,null,4]中，索引3为null表示节点2没有左子节点，但索引4的节点4仍然作为节点2的右子节点正确连接。这种表示法在堆（Heap）和线段树中非常常用，缺点是稀疏树会浪费较多空间。
问：递归遍历和迭代遍历各有什么优缺点？
答：递归实现代码简洁、容易理解，利用函数调用栈隐式维护遍历状态，但深度过大时可能导致栈溢出（Stack Overflow），且函数调用有一定性能开销。迭代实现使用显式栈（深度优先遍历）或队列（层序遍历），避免了栈溢出风险，性能通常更优，但代码复杂度较高。在工程实践中，对于平衡二叉树推荐使用递归实现（代码可维护性好），对于深度不确定的树推荐使用迭代实现。本工具展示的动画模拟了递归访问的过程，帮助用户直观理解递归遍历的执行逻辑。
问：二叉树遍历的实际应用场景有哪些？
答：前序遍历常用于序列化和反序列化二叉树、克隆树结构、前缀表达式求值；中序遍历常用于二叉搜索树的有序输出、验证BST的合法性；后序遍历常用于计算目录总大小、表达式树求值、垃圾回收中先处理子对象；层序遍历常用于无权图的最短路径搜索（BFS）、按层打印节点、连通性检测、社交网络中的距离计算。掌握不同遍历方式的适用场景，有助于在实际开发中选择最合适的算法策略。
问：为什么层序遍历需要使用队列而不能用栈？
答：层序遍历的目标是按深度层级从上到下、从左到右依次访问节点，这要求先访问的节点的子节点也要先被处理，符合先进先出（FIFO）的特性，因此需要使用队列。栈是后进先出（LIFO）的数据结构，如果用栈来实现层序遍历，会导致深度优先的行为，无法保证按层访问。实际操作中，先将根节点入队，每次出队一个节点时将其左右子节点依次入队，这样就能保证节点按照层序的顺序被依次访问。
问：如何利用中序遍历判断一棵树是否是二叉搜索树？
答：二叉搜索树（BST）的定义是：任意节点的左子树所有值小于该节点值，右子树所有值大于该节点值。对BST进行中序遍历会得到严格递增的有序序列。因此，判断一棵二叉树是否是BST的方法是：执行中序遍历，记录前一个访问的节点值，每次访问新节点时检查其值是否大于前一个节点值。如果所有节点都满足递增关系，则是合法的BST；否则不是。需要注意的是，不能仅凭「左子节点小于根、右子节点大于根」来判断，因为这无法检测到更深层的违规情况。
问：工具中的JSON数组输入应该怎样编写？
答：在工具的数组输入框中，你可以使用JSON格式的数组来定义二叉树结构。数组遵循层序编号规则：索引0是根节点，节点i的左子节点在2i+1，右子节点在2i+2。使用null表示空节点。例如输入[1,2,3,4,5,null,6]表示根节点为1，左子节点为2，右子节点为3，节点2的左子节点为4、右子节点为5，节点3没有左子节点（null）、右子节点为6。点击「应用」按钮后，左侧会渲染出对应的树形结构。
问：遍历动画中的三种颜色分别代表什么含义？
答：工具通过三种不同的颜色状态来标记节点的访问情况。灰色（默认颜色）表示「未访问」节点，即遍历过程尚未触及的节点；高亮色表示「正在访问」节点，即当前正在被处理的节点，用户可以观察到该节点处于遍历的焦点位置；已访问颜色表示「已访问」节点，即遍历过程中已经完成处理的节点。通过观察这三种颜色的变化过程，用户可以清晰地理解遍历算法的执行流程和访问顺序。