用非递归算法求二叉树高度

可以使用层序遍历的方式，从根节点开始，每遍历一层就把高度加1，直到遍历完所有层即可获得二叉树的高度。以下是示例代码：

int getHeight(Node* root) {
    if (root == nullptr) {
        return 0;
    }
    queue<Node*> q;
    q.push(root);
    int height = 0;
    while (!q.empty()) {
        int levelSize = q.size();
        for (int i = 0; i < levelSize; i++) {
            Node* node = q.front();
            q.pop();
            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
        height++; // 遍历完一层后，高度+1
    }
    return height;
}

对于二叉树的每个结点，都要访问一次，时间复杂度为 O(N)，其中 N 是二叉树的结点数；空间复杂度为 O(W)，其中 W 是最大的层宽。

相关问题

C语言中，借助链式队列，用非递归算法求二叉树的高度

求解二叉树的高度可以使用递归或非递归算法，下面是使用链式队列和非递归算法求解二叉树高度的步骤：

1. 定义一个结构体用于表示二叉树的结点，包含一个指向左子树的指针和一个指向右子树的指针。

typedef struct TreeNode {
    int value;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

2. 定义一个结构体用于表示队列中的元素，包含一个指向二叉树结点的指针和一个指向下一个元素的指针。

typedef struct QueueNode {
    TreeNode* node;
    struct QueueNode* next;
} QueueNode;

3. 定义一个链式队列，包含一个指向队头元素的指针和一个指向队尾元素的指针。

typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

4. 定义一个函数用于创建二叉树结点。

TreeNode* createTreeNode(int value, TreeNode* left, TreeNode* right) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->value = value;
    node->left = left;
    node->right = right;
    return node;
}

5. 定义一个函数用于计算二叉树的高度，该函数使用链式队列和非递归算法实现。

int calculateHeight(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    Queue queue;
    queue.front = NULL;
    queue.rear = NULL;
    QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
    node->node = root;
    node->next = NULL;
    queue.front = node;
    queue.rear = node;
    int height = 0;
    while (queue.front != NULL) {
        height++;
        int levelSize = queue.rear - queue.front + 1;
        for (int i = 0; i < levelSize; i++) {
            QueueNode* currentNode = queue.front;
            queue.front = queue.front->next;
            if (currentNode->node->left != NULL) {
                QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
                newNode->node = currentNode->node->left;
                newNode->next = NULL;
                queue.rear->next = newNode;
                queue.rear = newNode;
            }
            if (currentNode->node->right != NULL) {
                QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
                newNode->node = currentNode->node->right;
                newNode->next = NULL;
                queue.rear->next = newNode;
                queue.rear = newNode;
            }
            free(currentNode);
        }
    }
    return height;
}

6. 使用上述函数计算二叉树的高度。

int main() {
    // 构建二叉树
    TreeNode* root = createTreeNode(1,
        createTreeNode(2,
            createTreeNode(4, NULL, NULL),
            createTreeNode(5, NULL, NULL)),
        createTreeNode(3,
            createTreeNode(6, NULL, NULL),
            createTreeNode(7, NULL, NULL)));
    // 计算二叉树的高度
    int height = calculateHeight(root);
    printf("The height of the binary tree is %d\n", height);
    return 0;
}

输出结果为：

The height of the binary tree is 3

设二叉树采用二叉链表存放，设计非递归算法求二叉树的高度

非常好的问题！对于这个问题，我可以给你一个基于迭代的算法来求解。该算法使用一个栈来模拟递归过程，具体步骤如下：

1. 如果二叉树为空，直接返回0.
2. 初始化一个栈，将树的根节点入栈，高度初始化为1.
3. 循环执行以下步骤：
1. 如果栈为空，说明已经遍历完了整棵树，返回高度.
2. 取出栈顶元素，如果该节点没有孩子，则继续循环.
3. 否则，将左右孩子分别入栈，并将高度+1.
4. 完成算法.

这个算法和递归算法非常类似，但是由于使用了一个栈来模拟递归，所以是一个非递归算法。希望这个算法对你有所帮助！