求二叉树高度的算法运行原理是什么？代码中HL、HR如何获取高度？

你贴的这段是二叉树高度的标准递归实现，逻辑完全基于分治递归的思路：

int GetHeight(BinTree BT)
{
    int HL, HR, MaxH;

    if(BT)
    {
        HL = GetHeight(BT->Left);
        HR = GetHeight(BT->Right);
        MaxH = HL > HR ? HL : HR;
        return (MaxH + 1);
    }
    else
        return 0;
}

HL、HR的取值原理 #

HL和HR就是递归调用自身得到的子树高度：

• 计算当前节点左子树高度的时候，直接把左孩子作为新的根节点，传入GetHeight函数，返回结果就是左子树的高度，赋值给HL
• 右子树高度HR的计算逻辑完全一样，只是传入的参数是当前节点的右孩子

整个递归的逻辑本质是把「计算整棵树高度」的大问题，拆成「计算左子树高度」「计算右子树高度」两个相同逻辑的小问题，小问题的计算规则和大问题完全一致，所以直接复用同一个函数即可。

完整运行逻辑拆解 #

1. 递归终止条件 #

当传入的BT是空指针（代表当前是空树），直接返回0，这段代码里定义空树的高度为0。

2. 递归计算规则 #

只要当前节点不为空，就遵循「先算左、再算右、最后算当前节点高度」的后序遍历逻辑：

• 先递归算完左子树高度得到HL
• 再递归算完右子树高度得到HR
• 取两个子树高度的最大值，加1（加的1是当前节点自身占的一层），就是以当前节点为根的整棵树的高度

简单示例验证 #

拿只有1个根节点的树举例：

• 传入根节点，节点不为空，调用左孩子（空）返回0，HL=0
• 调用右孩子（空）返回0，HR=0
• 取最大值0加1，返回1，也就是单节点树的高度为1，符合预期。

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