红黑树高度计算方法中return height(root)-1里减1的含义是什么？
2026-8-10
为什么对外的height()方法要减1？
先拆解两个方法的计数逻辑差异：
内部height(Node<K,V> node)的计数规则
这个递归方法统计的是从当前节点到最远叶子节点的节点总数：
- 传入
null时返回0； - 非空节点会把左右子树的节点数各加1（加上当前节点），取最大值返回。
举个实际例子：
- 只有单个根节点时，调用
height(root)会返回1（左右子节点都是null，计算后左右高度都是0+1=1，最终返回1）； - 根节点带一个左子节点时，
height(root)会返回2（左子节点的height是1，加1后为2，最终返回2）。
对外height()的预期逻辑
这个方法要返回的是树的高度（以边数为定义）——这是多数场景下的常规定义：
- 空树高度为0；
- 单个节点的树没有边，高度为0；
- 根节点带一个子节点的树只有1条边，高度为1。
减1的核心作用
内部方法返回的是节点数，而节点数减1正好等于边数。比如：
- 单个节点：
1（节点数）-1=0（边数高度），符合预期； - 两个节点：
2（节点数）-1=1（边数高度），符合预期。
如果去掉减1，对外方法返回的就是节点数统计的高度，和行业常规的边数定义不符，会导致调用者拿到的结果不符合预期。
内容的提问来源于stack exchange，提问作者ZENA Lee
相关产品推荐
相关产品推荐
