关于C++递归函数计算二叉搜索树最大高度的执行流程疑问

我在观看YouTube上实现二叉搜索树的视频时，看到了这段计算树最大高度的函数，大致理解该函数如何获取高度，但对其执行流程不太清楚，想了解它的运行逻辑。我原以为函数在到达节点末尾时返回-1，然后逐层向根节点递增1？

函数代码 #

int MaxHeight(BstNode* root) {
    if (root == NULL) {
        return -1;
    }
    return max(MaxHeight(root->left),MaxHeight(root->right))+1;
}

运行逻辑拆解 #

• 终止条件的意义：当传入的节点是NULL（也就是某个节点的左/右子节点不存在时）返回-1，这是因为这段代码的高度是按「边的数量」计算的——叶子节点没有子节点，它的左右子调用都返回-1，取最大值后加1，刚好得到叶子节点的高度为0（符合边数定义）。如果是按「节点数量」算高度，这里应该返回0，对应叶子节点高度为1，这是两种不同的计数规则。
• 递归执行流程：函数是深度优先遍历的逻辑，会先一路递归到某条分支的最末端（碰到NULL），再回溯向上计算每一层的高度：
  1. 从根节点出发，先递归处理左子树的所有节点，直到左子树的某个节点的左/右子节点是NULL，触发终止条件返回-1；
  2. 回溯到上一层节点，计算它的左子树高度；接着处理该节点的右子树，同样递归到末端再回溯计算高度；
  3. 取左右子树的最大高度，加1就是当前节点的高度，再返回给上一层；
• 简单例子验证：
  • 只有根节点的树：调用MaxHeight(root)，root非空，调用左右子节点（都是NULL），返回-1，max(-1,-1)=-1，加1后返回0，也就是根节点高度为0（边数为0，符合定义）。
  • 根节点带一个左叶子节点：调用MaxHeight(root)，先处理左叶子节点：左右子节点都是NULL，返回-1，max后加1得到0（左叶子的高度）；再处理根的右子节点，返回-1；取max(0,-1)=0，加1得到1，也就是根节点高度为1（根到左叶子有1条边）。
• 你理解的「到达末尾返回-1，逐层向根递增1」是完全正确的，核心就是先递归到底触底返回，再回溯时每一层都把下一层的最大高度加1，最终传递到根节点得到整棵树的最大高度。

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