C++中二叉搜索树（BST）递归计算树高的实现疑问

你想不通的核心原因是把递归执行顺序搞反了 #

你默认递归是从根节点开始从上往下逐层计数，但实际上这段代码的递归是自底向上攒高度，根本不是从上往下数走了多少步。

能正确累加的两个关键基础 #

这两个细节藏在代码最开头，也是你纸面推演时很容易漏看的点：

• 代码一开始就给leftHeight、rightHeight设了默认值0：如果当前节点没有左/右孩子，对应方向的高度就一直保持0，根本不需要额外对空指针调用函数
• 树高的定义本身就写死了计算规则：任意节点的高度 = 1（自己所在的层） + max(左子树高度, 右子树高度)。这个规则天然就要求“先拿到子树的高度，再加当前节点的1层”，和你担心的顺序问题根本不冲突。

拿最简单的树走一遍真实执行流 #

就拿结构最简单的树举例：根节点A，左孩子B，右孩子C，B和C都是没有任何子节点的叶子。
你以为的执行顺序是：进根节点 → 给根加1 → 去左子树 → 左子树加1 → 一直往下钻。
但实际跑起来的顺序是这样的：

1. 进A的函数，初始化两个高度变量都是0
2. 看到左指针指了B，立刻停下当前层的所有计算，跳去执行B的getLength()——这时候A半点儿加1的操作都没做
3. 进B的函数，初始化两个高度都是0；因为B没有孩子，根本不需要再往下递归
4. B这一层已经没路可下了，直接算：两个方向高度都是0，返回max(0,0)+1=1——这就是B的高度，因为B自己占1层，左右啥都没有
5. 带着1这个返回值跳回A的执行层，把1存到A的leftHeight里，这时候你打印出来才会看到leftHeight:1
6. A看到右指针指了C，再停下当前计算，跳去跑C的getLength()
7. C和B一样是叶子，算完返回1，存到A的rightHeight里，打印出来rightHeight:1
8. 现在A已经拿到左右两个子树的真实高度了，才开始算自己的高度：比较1和1，返回max(1,1)+1=2——这就是整棵树的总高度，算出来完全正确。

为什么你会觉得“先递归再加1”有问题？ #

你把代码的书写顺序和实际执行的时间顺序搞混了。
代码里看起来是“先写递归调用拿子树值，再写+1返回”，但实际跑的时候，递归会一路扎到最底层的叶子才停，从叶子开始往上层退，每退一层才做一次+1的操作——这个+1加的就是当前节点自己占的那一层，根本不会出现重复累加或者漏算的情况。
顺带说一句，这段代码里的空判断if (!prev && !dataInit) return 0;其实是冗余的：因为只有当left/right指针非空的时候才会触发递归，空指针根本不会被调用到这个函数里，这个分支在实际运行时永远走不到。

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