递归树遍历算法时间复杂度分析：节点基数设置算法递推关系疑问

算法基础逻辑 #

你实现的是通过后序遍历计算每个节点对应子树的节点总数，每个节点仅会被访问一次，空指针也会被访问一次，算法本身无额外遍历开销。

注：你提供的伪代码存在变量名笔误，x.left_child、x.right_child需要修正为node.left_child、node.right_child，修正后的代码如下：

SetCardinality(node)
 if node exists:
   node.card = 1 + SetCardinality(node.left_child) + SetCardinality(node.right_child)
   return node.card
 else:
   return 0

最坏场景定义 #

你提到的最坏输入是高度为n的树，指的是退化为单链表的斜树：每个节点仅存在一个子节点，树的总节点数等于树的高度，即总节点数为n。

递推式T(n) = T(n-1) + n的对应关系 #

该递推式的定义前提是针对上述斜树场景，其中各参数含义如下：

• n：当前待计算的斜树的总节点数，也等于该斜树的高度
• T(n)：计算总节点数为n的斜树所有节点cardinality属性的总时间开销
• T(n-1)：递归计算当前节点唯一非空子树（总节点数为n-1的斜树）的时间开销
• 末尾的n：该定义下计入的全链路附加操作总开销，包含每一层递归的节点存在性判断、属性赋值、结果返回操作的累加，每一层固定1次操作，n层总共有n次附加操作。

补充说明：行业通用的复杂度分析中，会将单次递归的附加操作视为O(1)常数，得到的递推式为T(n) = T(n-1) + O(1)，求解后时间复杂度为O(n)，和实际运行开销一致，和上述递推式的最终复杂度结论没有差异。

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