关于二叉树节点深度计算算法的时间复杂度疑问咨询

问题描述 #

需要计算二叉树中节点的深度，定义规则如下：

• 空树的深度为-1
• 节点的深度 = 其父节点深度 + 1

输入为节点v，输出为v的深度，算法实现如下：

Procedure Depth(v)
    if v = null then
        return −1
    return 1 + Depth(v.parent)

疑问：该算法的时间消耗依赖于树的规模，那它的时间复杂度是O(n)吗？还是因为树的规模固定所以是O(1)？又或是因为未遍历半数以上节点所以是O(log(n))？

详细解释 #

时间复杂度的分析核心是看算法执行的操作次数与输入规模、最坏情况的关系，这里的关键是算法的执行次数等于节点v到根节点的路径长度（含v到根的所有节点，再加上一次null的判断），我们分情况讨论：

• 最坏情况：链式二叉树（单支树）
  如果二叉树是链式结构（每个节点只有一个子节点，整体像一条链表），当v是最底层的节点时，它到根的路径长度等于树的总节点数n（比如n个节点的链式树，最深节点的深度是n-1，算法需要递归调用n次：从v到根共n个节点，再加上一次null的判断）。此时时间复杂度为O(n)。

• 平衡二叉树场景
  如果是完全平衡的二叉树（每个节点的左右子树高度差不超过1），树的高度为O(log n)（n为总节点数）。此时即使v是最深层的节点，它到根的路径长度也是O(log n)，算法的递归调用次数为O(log n)，时间复杂度为O(log n)。

• 关于O(1)的误解
  只有当v是null或者根节点时，算法的执行步骤是常数次，但这是个别输入的情况，不是时间复杂度的衡量标准。时间复杂度描述的是算法在最坏情况或平均情况下的性能，不会因为树的规模固定就判定为O(1)——除非所有可能的输入v对应的路径长度都是常数，但显然在多数树结构中不成立。

• 关于“未遍历半数节点”的误区
  时间复杂度的判断不依赖于是否遍历了半数以上节点，而是看算法实际执行的操作次数与输入规模的关系。这个算法只沿着v到根的单一路径执行，不会遍历其他节点，所以操作次数只和这条路径的长度相关，和树的总节点数没有直接的线性关系，除非是链式树这种极端情况。

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