假设二叉树采用二叉链表存储结构，设计一个算法计算给定二叉树中双分支结点（度为 2 的结点）的数量。

[tag_link]

参考答案

递归统计左右子树，再在当前结点左右孩子都非空时加 1。

伪代码

CountDegree2(T):
    if T == null: return 0
    self = 1 if T.left != null and T.right != null else 0
    return self + CountDegree2(T.left) + CountDegree2(T.right)

复杂度

每个结点访问一次，时间 O(n)；递归栈空间 O(h)，最坏 O(n)。

边界条件

空树返回 0；叶结点和只有一个孩子的结点都不计数。

易错点

“双分支结点”要求两个孩子均存在，不能把度为 1 的结点算入，也不能使用逻辑或。

评分要点

空树递归出口；左右孩子同时非空才加 1；合并两棵子树计数；复杂度正确。