迭代法求二叉樹高度

---

二叉樹是一種資料結構。二叉樹的每個節點包含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) 用於在佇列中儲存節點。

迭代方法總是比遞迴方法更快地解決任何問題。在這裡，我們使用迴圈和佇列迭代地找到二叉樹的最大深度或高度。但是，程式設計師可以嘗試編寫遞迴方法的程式碼來查詢二叉樹的高度。