设二叉树采用二叉链表存放,设计非递归算法求二叉树的高度,给出代码
时间: 2024-01-23 16:46:49 浏览: 79
二叉树的高度可以通过非递归的方式求解,采用层次遍历算法可以实现。具体思路如下:
1. 从根节点开始,将其入队列;
2. 当队列不为空时,对队列头节点进行处理:
- 将其非空左右子节点入队列;
- 对队列中的所有节点进行计数,并记录层数;
3. 返回二叉树的高度,即为最后记录的层数。
下面是代码实现:
```python
def get_tree_height(root):
if not root:
return 0
height = 0
queue = [root]
while queue:
size = len(queue)
height += 1
for i in range(size):
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return height
```
注意,以上代码仅适用于二叉树采用二叉链表存放的情况。对于其他存储结构,需要根据实际情况进行修改。
阅读全文