如何返回指定节点左右子树的in-order traversal数组?递归代码未过测试求排查
代码错误定位
你对中序遍历的顺序逻辑判断没有问题,测试全部不通过的核心原因是Java基本类型的值传递机制导致数组索引跟踪完全失效。
具体问题拆解
- 私有递归方法中的
cur是int基本类型,方法调用时传递的是参数副本,不是参数本身的引用。你在当前方法栈内做的cur++操作,只会修改当前栈的副本值,完全无法把更新后的索引位置回传给上层调用栈。 - 实际运行时的表现:每一层递归调用拿到的
cur都是初始传入的0,所有遍历到的节点会反复往数组的第0位写入,直接覆盖之前存下的节点,数组后续位置要么保持null,要么填充顺序完全错乱,和测试用例预期的中序遍历顺序完全不匹配。
举个最简单的测试场景:如果指定的子树是根节点带左右两个叶子的三层结构,预期中序结果为「左叶子、根节点、右叶子」。按你现有代码执行,最终数组会变成「根节点、右叶子、null」——根节点会把之前存好的左叶子覆盖掉,完全对不上预期输出。
修正方案
不需要大改整体逻辑,只需要调整递归方法的索引传递方式,让每一层递归把当前填充完成后的最新索引逐层回传即可。
修正后的私有递归方法参考:
private int enumerateNodes(TreeNode node, TreeNode[] arrays, int cur){ if(node == null){ return cur; } // 递归处理左子树,拿到左子树部分填充完成后的最新索引 cur = enumerateNodes(node.left, arrays, cur); // 在当前索引位置存入节点,索引后移 arrays[cur++] = node; // 用更新后的索引递归处理右子树 cur = enumerateNodes(node.right, arrays, cur); // 把最新索引返回给上层调用栈 return cur; }
原有公有方法的逻辑不需要修改:你在公有方法里根据传入的child方向选择左/右子树作为遍历起点、根据节点总数初始化数组长度的逻辑都是正确的,只要修正递归方法的索引传递问题,就能正确生成对应子树的中序遍历数组。
如果不想调整递归方法的返回值,也可以用长度为1的int数组(或者AtomicInteger)作为可变索引容器跟踪当前填充位置,效果完全一致。
内容的提问来源于stack exchange,提问作者Foc Dr
相关产品推荐
相关产品推荐

