假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树的高度
时间: 2023-04-27 08:06:20 浏览: 185
可以使用层次遍历的方式来求二叉树的高度。具体步骤如下:
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;
}
```