在不使用递归的情况下,可以使用迭代的方式来找到二叉树的高度。具体的实现方法是使用层序遍历算法,通过队列来遍历二叉树的每一层节点,并记录层数,直到遍历完所有节点。
以下是实现的代码示例:
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
typedef struct QueueNode {
TreeNode* node;
struct QueueNode* next;
} QueueNode;
typedef struct Queue {
QueueNode* front;
QueueNode* rear;
} Queue;
Queue* createQueue() {
Queue* queue = (Queue*)malloc(sizeof(Queue));
queue->front = NULL;
queue->rear = NULL;
return queue;
}
void enqueue(Queue* queue, TreeNode* node) {
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
newNode->node = node;
newNode->next = NULL;
if (queue->rear == NULL) {
queue->front = newNode;
queue->rear = newNode;
} else {
queue->rear->next = newNode;
queue->rear = newNode;
}
}
TreeNode* dequeue(Queue* queue) {
if (queue->front == NULL) {
return NULL;
}
TreeNode* node = queue->front->node;
QueueNode* temp = queue->front;
queue->front = queue->front->next;
if (queue->front == NULL) {
queue->rear = NULL;
}
free(temp);
return node;
}
int getBinaryTreeHeight(TreeNode* root) {
if (root == NULL) {
return 0;
}
Queue* queue = createQueue();
enqueue(queue, root);
int height = 0;
while (1) {
int levelSize = queue->rear - queue->front + 1;
if (levelSize == 0) {
break;
}
while (levelSize > 0) {
TreeNode* node = dequeue(queue);
if (node->left != NULL) {
enqueue(queue, node->left);
}
if (node->right != NULL) {
enqueue(queue, node->right);
}
levelSize--;
}
height++;
}
return height;
}
int main() {
// 构造二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->left->val = 4;
root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
root->left->right->val = 5;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right->left->val = 6;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 7;
// 计算二叉树的高度
int height = getBinaryTreeHeight(root);
printf("二叉树的高度为:%d\n", height);
// 释放内存
free(root->right->right);
free(root->right->left);
free(root->left->right);
free(root->left->left);
free(root->right);
free(root->left);
free(root);
return 0;
}
在上述代码中,我们定义了一个队列结构和一个二叉树结构,使用队列进行层序遍历。首先创建一个队列,并将根节点入队。然后进行循环,当队列非空时,先获取当前层的节点数,依次出队并将它们的左右子节点入队。在每一层处理完之后,层数加1,直到队列为空。最后返回层数作为二叉树的高度。
这里没有提及具体的腾讯云相关产品,因为找二叉树高度是一般计算问题,与云计算平台的关系不大,因此不需要特定的云计算产品来解决。
领取专属 10元无门槛券
手把手带您无忧上云