[C++知识库][C] PTA 6-8 求二叉树高度

本题要求给定二叉树的高度。

函数接口定义：

int GetHeight( BinTree BT ); 

其中BinTree结构定义如下：

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

要求函数返回给定二叉树BT的高度值。

思路：

二叉树的高度就是根节点的高度。

已知当前结点高度=子树高度最大值+1，所以递归求一下左右子结点（左右子树）高度就好。

时间复杂度：O(N) N是结点数?

空间复杂度：O(N)

int GetHeight( BinTree BT ){
    int hl=0;
    int hr=0;
    int h=0;
    
    if(BT==NULL){
        return 0;
    }
    
    hl=GetHeight(BT->Left);//求左子树高度
    hr=(GetHeight(BT->Right));//求右子树高度
    
    if(hl>hr){
        h=hl+1;
    }else{
        h=hr+1;
    }
    return h;
}

以下是发文助手嫌我文章太短所以瞎打的字：

递归是比较容易理解的方式。

那么这道题除了递归还有其他的方法吗？

树的高度也可以理解为层数。可以尝试用层序遍历的思路求树的高度。

如果结点结构体里能有一个变量记录当前结点在第几层就好了——诶，data不就可以？毕竟这道题没要求输出结点的数据，所以data可以随便篡改

创建使用一个队列，根节点赋值为１，使其入队；左右孩子赋值为２，入队．．．．．．

即：子节点data值=父节点data值+1，并进入队列。

设一个int变量h。对队列遍历，如果比h大就赋给h。

入队+出队的时间复杂度： O(N)

空间复杂度：O(N)

......真是没有必要的优化呢，优化了个寂寞