二叉树4：二叉树求树高度(超级详细)

一、思路

什么是树高？
树的高度(或深度)就是树中结点的最大层数。

在这里使用后序遍历的递归算法。

对每一个结点都进行如下操作：

• 后序遍历其左子树求树高
• 后序遍历其右子树求树高
• 对这个结点进行下面操作：
  • 比较其左右子树的高度大小
  • 若左>右，则选择左的高度；反之，选择右的高度
  • 将上一步选出的高度+1，并作为返回值返回

递归算法比较抽象，这里举个例子

比如上面这个图，按照后序遍历的序列，第1个遍历到的会是①这个结点。
然后，对①进行上面的处理。

• ①左子树高度为0，右子树高度为0
• 比较左右子树大小，若左大于右，则选择左。此时，左不大于右，那么选右：0
• 对0+1，然后将1返回给上一层。即就是，作为结点④其左子树的高度返回上去。

第2个遍历到的是②这个结点：
同样的道理，可以得到②结点会返回给上一层1。

第3个遍历的是④结点:
遍历到④的时候，其左右子树的高度已经由前两步骤得出来了，都是1。
接着，对4进行同样的操作，比较其左右子树的高度。
若左子树高于右子树，就选择左子树的高度，否则选择右子树。
这里左右都是1。那么选右子树的1。
接着，1+1=2。

这个结果就是遍历根节点⑤的左子树所得到的结果。

然后用同样的方式遍历右子树，最后回到根节点。
对根节点的处理方式也相同:
比较左右树的高度，选高的，然后+1返回最终的结果就是树高。

二、代码实现

这个是代码实现，如果看不明白的，上去看看对每个结点处理的方式，和上面举的例子

typedef struct TreeNode{
	int data;//数据域
	TreeNode *RChild;//右孩子指针
	TreeNode *LChild;//左孩子指针
}TreeNode, *BiTree;

int getdepth(TreeNode* node) {
    //1.确定递归函数的返回值和参数：参数-传入根节点 返回值-int
    //2.终止条件：如果为空节点，返回0，表示高度为0
    if (node == NULL) return 0;
    //3.确定单层递归的逻辑
    int leftdepth = getdepth(node->LChild);//递归求左子树高度
    int rightdepth = getdepth(node->RChild);//递归求右子树高度
    //int depth = 1 + max(leftdepth, rightdepth);//树的高度是根到叶子最长路径上的结点的数量
    int depth = 1 + (leftdepth > rightdepth?leftdepth:rightdepth);//这样写和上一行一样
    //所以，每次要找最高的那个子树，所以要使用max函数
    //调用两个递归函数直接可以算出来两个子树的高度，取最高的子树就作为子树高度，再加上根节点高度就行
    return depth;//在这个题目中，我们认为的高度是从根节点到叶子节点最长路径上结点的数量
    //所以，如果这个二叉树只有一个节点，那么这个树的高度就是1
}