LeetCode105题前序中序构建二叉树参考代码运行报错排查

• 核对官方题解的边界条件处理
  检查递归终止逻辑，比如当preorder_start > preorder_end或inorder_start > inorder_end时是否直接返回None。如果终止条件写错（比如用了>=而非>），递归到某一步时会尝试访问不存在的列表元素，直接触发索引越界。

• 验证根节点的中序索引计算
  官方题解一般会用哈希表缓存中序元素的索引，先确认这个哈希表的构建是否正确。比如你的测试用例inorder = [6,1,8,4,3]，哈希表中各元素对应的索引应该是6:0、1:1、8:2、4:3、3:4。如果哈希表构建出错，找根节点索引时会得到错误值，导致后续分割左右子树的索引范围完全混乱。

• 检查左右子树的索引范围划分
  重点看递归调用时的索引参数是否符合逻辑：

  • 左子树的前序范围：preorder_start + 1 到 preorder_start + left_size（left_size = inorder_root - inorder_start）
  • 左子树的中序范围：inorder_start 到 inorder_root - 1
  • 右子树的前序范围：preorder_start + left_size + 1 到 preorder_end
  • 右子树的中序范围：inorder_root + 1 到 inorder_end
    手动模拟第三步时，把这些索引值算出来，看是否出现索引超出数组长度的情况（比如preorder_end设为5，但数组最大索引是4）。

• 打印关键索引调试
  在递归函数里，每次调用时打印当前的preorder_start、preorder_end、inorder_start、inorder_end以及根节点的中序索引。对比手动模拟的数值，定位哪一步的索引突然超出合法范围。

• 确认测试用例的合法性
  题目要求输入的前序和中序遍历必须对应同一棵二叉树，且无重复元素。你的测试用例preorder = [4,1,3,6,8]、inorder = [6,1,8,4,3]本身存在矛盾：
  根节点是4，中序中4的左子树是[6,1,8]，右子树是[3]。按照前序遍历规则，4之后应该先遍历左子树的全部节点，再遍历右子树。但你的前序中4之后是1、3，3是右子树的根，提前出现在左子树遍历位置，属于非法输入。官方题解是基于合法输入编写的，非法输入会导致索引计算逻辑失效，触发越界错误。

内容的提问来源于stack exchange，提问作者Hyrenthejoker