二叉树的高度#

一、引言#

开始之前我们来回顾一下树的高度：被定义为从根节点到最长叶子的距离。（因此一棵树的高度可以说是根节点的高度）。

高度：可以被定义为该节点到一个叶子节点的最长路径上的边数。

很显然，高度和叶子节点有关。

他常常和深度放在一起，导致二者极其容易被混淆。

深度指的是：从根节点到当前节点走的边数。

树的高度等于树中节点的最大深度。

二、cpp实现#

本文将带着大家实现查看一棵树的高度。

对于根节点来说，左子树的高度为2，右子树的高度为1。而整棵树的高度为3。

所以一棵树的高度就是max（左子树高度，右子树高度）+1。

利用这个公式，我们来模拟一下。

1
int findheight(BstNode *root){
2
    if(root==NULL){//处理空树的情况，同样也是递归停止条件。
3
        return 0;
4
    }
5
    leftheight=findheight(root->left);
6
    leftheight=findheight(root->left);
7
  return max(leftheight,righthight)+1;
8
}

这合理吗？不合理！

还是这张图，假设传入函数的是节点7.那么他会走两次递归，左树和右子树都为NULL。都返回0。

然后leftheight,righthight都是0，最后+1得到高度为1。但是这对吗？7明明是高度为0！

所以返回0并不正确！返回-1才是合理的。

正确代码如下

1
#include<iostream>
2
using namespace std;
3
struct BstNode{
4
    int data;
5
    BstNode *left;
6
    BstNode *right;
7
};
8
int findheight(BstNode *root){
9
    if(root==NULL){//处理空树的情况，亦是递归终止条件
10
        return -1;
11
    }
12
    return max(findheight(root->left),findheight(root->right))+1;
13
}
14
int main(){
15
    BstNode *root=NULL;
16
    int height = findheight(root);
17
    cout<<height;
18
}