迭代法求二叉树高度

---

二叉树是一种数据结构。二叉树的每个节点包含0、1或2个子节点。因此，二叉树可以包含多个层次。

这里，我们需要使用循环编写迭代代码来查找二叉树的高度。二叉树中的总层数代表二叉树的高度。或者，我们可以说从根节点到二叉树的最大深度就是二叉树的高度。

问题陈述 - 我们给定一个二叉树。我们需要使用迭代方法来查找给定二叉树的高度。

方法一

如上所述，二叉树的高度等于二叉树的总层数。我们将使用队列数据结构遍历每一层的每个节点，并找到树的最大深度。

算法

步骤1 - 定义 'treeNode' 类，并添加 'val' 整型变量。还在类中定义 'left' 和 'right' 指针。

步骤2 - 定义 createNode() 函数来为树创建新节点。它创建一个新的 treeNode，用参数值初始化 'val'，用空值初始化 left 和 right 指针。最后，它返回新创建的节点。

步骤3 - findHeight() 函数用于查找二叉树的高度。

步骤4 - 定义队列 'levelqueue' 用于存储当前层的所有节点，'treeHeight'，'n_cnt' 变量和 'temp' 节点。

步骤5 - 如果头节点为空，则返回 0。

步骤6 - 将头节点推入 'levelQueue'。

步骤7 - 使用 'while' 循环进行迭代，直到 'levelQueue' 变为空。

步骤8 - 将 'treeHeight' 加 1，并将 'n_cnt' 初始化为队列的大小，表示当前层中的总节点数。

步骤9 - 遍历队列的所有元素。

步骤9.1 - 弹出队列的第一个元素。

步骤9.2 - 如果当前节点存在左子节点，则将其插入队列。

步骤9.3 - 如果当前节点存在右子节点，则将其插入队列。

步骤9.4 - 从队列中移除第一个节点。

步骤10 - 返回 'treeHeight' 变量的值。

示例

#include <iostream>
#include <queue>

using namespace std;
class treeNode {
public:
    int val;
    treeNode *left;
    treeNode *right;
};
treeNode *createNode(int val) {
    //Create a new node
    treeNode *temp = new treeNode();
    temp->val = val;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
int fidHeight(treeNode *head) {
    queue<treeNode *> levelQueue;
    int treeHeight = 0; // To store the tree height of the current binary tree
    int n_cnt = 0;      // To store the total number of current level nodes.
    treeNode *temp;     // Pointer to store the address of a node in the current level.
    // For empty binary tree
    if (head == NULL) {
        return 0;
    }
    // Add root node to queue
    levelQueue.push(head);
    // Traverse level of binary tree
    while (!levelQueue.empty()) {
        // For each level increment, the treeHeight of the three
        treeHeight++;
        n_cnt = levelQueue.size();
        // Add child nodes of all nodes at the current level
        while (n_cnt--) {
            temp = levelQueue.front();
            // Insert the left child node of the current node
            if (temp->left != NULL) {
                levelQueue.push(temp->left);
            }
            // Insert the right child node of the current node
            if (temp->right != NULL) {
                levelQueue.push(temp->right);
            }
            // remove the current node
            levelQueue.pop();
        }
    }
    return treeHeight;
}
int main() {
    treeNode *head = NULL;
    // Adding nodes to binary tree.
    head = createNode(45);
    head->right = createNode(32);
    head->right->left = createNode(48);
    head->left = createNode(90);
    head->left->left = createNode(5);
    head->left->left->left = createNode(50);
    cout << "The given binary tree's treeHeight is " << fidHeight(head) << ".";
    return 0;
}

输出

The given binary tree's treeHeight is 4.

时间复杂度 - O(N) 遍历每个节点。

空间复杂度 - O(N) 用于在队列中存储节点。

迭代方法总是比递归方法更快地解决任何问题。在这里，我们使用循环和队列迭代地找到二叉树的最大深度或高度。但是，程序员可以尝试编写递归方法的代码来查找二叉树的高度。