为什么该二叉树高度递归计算函数返回值为3，是否为正确结果？

问题原因 #

你手动计算的基准规则和函数实际的递归终止条件不一致，导致结果差了1。

函数规则明确 #

你写的高度函数逻辑是固定的：

fun height(node: BinaryNode<T>? = this): Int {
    return node?.let { 
        1 + max(height(node.leftChild), height(node.rightChild)) 
    } ?: -1
}

• 终止条件：如果节点为空（null），直接返回 -1
• 非空节点计算规则：当前节点高度 = 1 + 左、右子树高度的最大值

逐层计算验证 #

从最底层的叶子节点往根节点推：

• 节点4、6、9都没有子节点，左右都是空，高度 = 1 + max(-1, -1) = 0
• 节点5的左孩子是6（高度0），右孩子为空（高度-1），高度 = 1 + max(0, -1) = 1
• 节点3的左孩子是4（高度0），右孩子是5（高度1），高度 = 1 + max(0, 1) = 2
• 根节点1的左孩子是3（高度2），右孩子是9（高度0），高度 = 1 + max(2, 0) = 3

你手动算错的根源 #

你标注在节点旁括号里的数值，是默认「空节点返回0」算出来的结果：如果空节点返回0，叶子节点高度就变成1 + max(0,0) =1，最终根节点高度就是2，刚好和你手动推算的结果一致。但函数实际的终止条件是空节点返回-1，所以最终结果会多1。

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