求二叉树的高度算法设计思想
时间: 2024-01-23 07:14:47 浏览: 19
求二叉树的高度可以使用层次遍历的算法。算法的设计思想是通过设置变量level记录当前节点所在的层数,设置变量last指向当前层最右边的节点。每次层次遍历出队时,与last指针作比较,若两者相等,则层数加1,并让last指向下一层的最右节点,直到遍历完成。最后,level即为二叉树的高度。
以下是一个示例算法实现:
```python
def btDepth(bt):
if not bt:
return 0 # 若二叉树为空则返回0
front = -1
rear = -1 # 用front,rear双指针分别指向当前层遍历到的节点数和下一层节点中共有的节点数
last = 0
level = 0 # last指向当前层的节点总数
Q = [bt]
while front < rear:
p = Q[front + 1] # 将当前遍历到的节点出队
if p.lchild:
Q.append(p.lchild)
rear += 1
if p.rchild:
Q.append(p.rchild) # 若有左右节点入队
rear += 1
if front == last: # 如果当前遍历到的节点已经是当前层最后一个节点,则更新last为下一层的节点数,并且将层数加1
level += 1
last = rear
return level
```