为何拆分函数实现中序遍历(Inorder traversal)可行,单函数却失效?
单函数实现二叉树中序遍历失败的常见原因
结果集合的重复创建/重置问题
拆分辅助函数时,通常会在主函数中初始化一次结果列表,所有递归调用共享这个列表进行节点值的添加。但单函数实现时,若每次递归都新建结果列表(比如在函数开头声明List<Integer> res = new ArrayList<>()),会导致每次递归生成独立的列表,之前遍历的节点数据无法累积,最终返回的只是最后一次递归的局部结果。递归返回值的拼接逻辑错误
中序遍历遵循左→根→右的顺序,单函数实现时需正确合并左子树遍历结果、当前节点值、右子树遍历结果。很多错误写法会直接丢弃左子树的遍历结果:比如仅调用inorderTraversal(root.left)却不将其返回的列表合并到当前结果中,最终返回的只有当前节点和右子树的结果,左子树数据完全丢失。示例错误代码:public List<Integer> inorderTraversal(TreeNode root) { if (root == null) return new ArrayList<>(); inorderTraversal(root.left); // 左子树结果未被使用 List<Integer> res = new ArrayList<>(); res.add(root.val); res.addAll(inorderTraversal(root.right)); return res; }递归状态的连续性断裂
辅助函数写法中,结果列表由外层函数持有,所有递归调用操作同一个列表,状态是连续累积的。但单函数实现时,若仅依赖返回值传递结果而未正确合并,会导致每一层递归的状态独立,无法形成完整的遍历序列。
内容的提问来源于stack exchange,提问作者Anonymous
相关产品推荐
相关产品推荐

