求二叉树的高度(递归和非递归)

假设二叉树采用二叉链表存储结构，设计一个算法求二叉树的高度。

递归：

int getTreeHight(BiTree T){if(T==NULL){return 0;}else {int lh = getTreeHight(T->lchild);int rh = getTreeHight(T->rchild);return (lh>rh?lh:rh)+1;}}

时间复杂度O(n)；空间复杂度O（n）

非递归

思想：先获得当前层的节点个数，遍历完队列中的节点就是处理完该层。这时候队列中所有节点就是下一层的。每处理一层，层数+1

int getTreeHight(BTree T){//树空 if(T==NULL){return 0;}//初始化队列 BTiree Q[MaxSize];int rear=-1,front=-1;Q[++rear]=T;//根入队 BTiree p;int last=0;//指向当前层最后一个结点 int count=0;//记录层数 while(front<rear){p=Q[++front];if(p->lchild){Q[++rear]=p->lchild;}if(p->rchild){Q[++rear]=p->rchild;}//当前层结点访问完毕，rear刚好指向下一层的最后一个结点 if(front==last){count++;last=rear;//指向下一层最后一个结点 }}return count;
}

时间复杂度O(n)；空间复杂度O（n）