设二叉树采用二叉链表存放,设计非递归算法求二叉树的高度,给出代码
时间: 2024-01-23 13:46:49 浏览: 19
二叉树的高度可以通过非递归的方式求解,采用层次遍历算法可以实现。具体思路如下:
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
```
注意,以上代码仅适用于二叉树采用二叉链表存放的情况。对于其他存储结构,需要根据实际情况进行修改。
相关问题
设二叉树采用二叉链表存放,设计非递归算法求二叉树的高度
非常好的问题!对于这个问题,我可以给你一个基于迭代的算法来求解。该算法使用一个栈来模拟递归过程,具体步骤如下:
1. 如果二叉树为空,直接返回0.
2. 初始化一个栈,将树的根节点入栈,高度初始化为1.
3. 循环执行以下步骤:
1. 如果栈为空,说明已经遍历完了整棵树,返回高度.
2. 取出栈顶元素,如果该节点没有孩子,则继续循环.
3. 否则,将左右孩子分别入栈,并将高度+1.
4. 完成算法.
这个算法和递归算法非常类似,但是由于使用了一个栈来模拟递归,所以是一个非递归算法。希望这个算法对你有所帮助!
假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树的高度
可以使用层次遍历的方式来求二叉树的高度。具体步骤如下:
1. 定义一个队列,将根节点入队。
2. 定义一个变量level,表示当前遍历到的层数,初始化为1。
3. 当队列不为空时,进行如下操作:
a. 记录当前队列的长度size。
b. 将队列中的所有节点依次出队,并将它们的左右子节点入队。
c. 当遍历完当前层的所有节点后,level加1。
4. 当队列为空时,返回level-1,即为二叉树的高度。
代码实现如下:
```
int getHeight(TreeNode* root) {
if (root == nullptr) {
return ;
}
queue<TreeNode*> q;
q.push(root);
int level = 1;
while (!q.empty()) {
int size = q.size();
for (int i = ; i < size; i++) {
TreeNode* node = q.front();
q.pop();
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
level++;
}
return level - 1;
}
```