6-8求二叉树高度

题目描述

求给定二叉树的高度

题目地址为:https://pintia.cn/problem-sets/15/problems/731

BinTree结构定义

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

思考

递归思想

对整棵树而言，就是根和左右子树。那么此时二叉树的高度为左右子树最高的那棵树加1就为整棵树的高度

以此类推（这一步可能会有点难以理解）

怎么说呢？递归到倒数第二阶段不就是一个结点了嘛！然后这个高度为1，怎么得到的呢？

这是通过对于两个空左右子树返回高度为0然后加上自身的1得到的，所有出口就是对空树返回0

具体代码

int GetHeight( BinTree BT ) {
    if (!BT) {
        return 0;
    }
    int h_left = GetHeight(BT->Left);
    int h_right = GetHeight(BT->Right);
    return (h_left > h_right ? h_left  : h_right) + 1;
}