类BST结构递归插入简化代码与原始代码差异疑问

云原生阿岚

2026-9-28

结论先行

两种实现的渐进时间复杂度完全一致，都是O(h)（h为BST高度，平均情况O(logn)，最坏链表状树为O(n)），差异只在常数开销和边界兼容性上，和复杂度等级无关。

你遗漏的关键细节

递归深度多1层，有栈溢出风险
你的简化代码把「判断子节点是否为空」的逻辑下沉到了下一层递归里：当发现要插入的左/右子节点是空列表时，你没有直接赋值，而是把这个空列表作为参数传入下一次递归，多做了一次函数调用。
当树的高度接近Python默认递归深度限制（默认1000）时，比如刚好是1000层的链表状BST，原始代码递归1000次即可完成插入，你的代码需要1001次，会直接触发RecursionError栈溢出。
常数执行效率更低
原始代码遇到空子节点时直接赋值结束流程，你的代码需要多走一次函数入栈、参数传递、空判断、列表extend的流程，单次插入的常数开销更高，插入操作越频繁，性能差异越明显。
逻辑可读性更差，不符合常规BST实现思维
常规BST插入的通用逻辑就是：当前节点非空时，判断插入方向，若目标方向子节点为空则直接插入，不为空才递归向下。原始代码和通用逻辑完全对齐，其他开发者可以一眼看懂。你的简化把边界判断下沉了一层，逻辑更绕，维护成本更高。
兼容性更差
你的实现强依赖「空节点用可变空列表[]表示」的约定，如果后续需求调整为空节点用不可变的None表示，你的代码会直接报错（传入None时T == []不成立，取T[0]直接抛出类型错误），而原始代码只需要修改判断空子节点的条件即可适配。