迭代方法寻找二叉树的高度

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

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

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

方法 1

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

算法

第 1 步 - 定义“treeNode”类，并添加“val”整型变量。另外，在类中定义“左”和“右”指针。

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

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

第 4 步 - 定义“levelqueue”队列来存储当前级别的所有节点、“treeHeight”、“n_cnt”变量和“temp”节点。

第 5 步− 如果头节点为 Null，则返回 0。

第 6 步- 将头节点推送到“levelQueue”。

第 7 步- 使用“while”循环进行迭代，直到“levelQueue”变空。

LALAL.AI

AI人声去除器和声乐提取工具

下载

第 8 步- 将“treeHeight”增加 1，并用队列的大小初始化“n_cnt”，代表当前级别的总节点数。

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

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

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

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

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

第 10 步- 返回“treeHeight”变量的值。

示例

#include 
#include 

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 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) 在队列中存储节点。

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