求二叉樹高度的迭代方法


難度級別
經常問 ol石 土磚 亞馬遜 狂徒 風箏 遠足 Snapdeal 朝聖
二叉樹 隊列

問題陳述

問題“找到二叉樹高度的迭代方法”指出您得到了一個 二叉樹,使用迭代方法找到樹的高度。

範例檔案

輸入
求二叉樹高度的迭代方法

3

輸入
求二叉樹高度的迭代方法

4

二叉樹高度的迭代法算法。

一棵樹的高度也等於 等級數 在樹上。 因此,要使用迭代找到高度,請執行 級別順序遍歷 樹的數量,併計算其中的級別數。

  1. 創建一個 隊列 並把根推向它。 將高度初始化為0。
  2. 當隊列不為空時,請重複步驟3和4。
  3. 此時,隊列包含樹的一級。 將高度增加1。將變量大小初始化為隊列的大小。
  4. 運行一個從1到大小的循環,並在每次迭代時從隊列中刪除一個元素並將其子級推入隊列。 此步驟將從隊列中刪除一個級別,並將下一個級別推送到該隊列。
  5. 返回高度。

解釋

考慮第一個示例中顯示的樹,

STEP 1:

將root推送到隊列中並將高度初始化為0,即,
隊列= 2,高度= 0

STEP 2:

隊列不為空時,請重複步驟3和4。

步驟3和4:

迭代1:
隊列包含第一級樹。
遞增高度,因此高度= 1。
刪除隊列中的所有元素,並將其子級添加到隊列中。
隊列= 7-> 11

迭代2:
隊列包含樹的第二層。
遞增高度,因此高度= 2。
刪除隊列中的所有元素,並將其子級添加到隊列中。
隊列= 5-> 9-> 3

迭代3:
隊列包含樹的第三層。
遞增高度,因此高度= 3。
刪除隊列中的所有元素,並將其子級添加到隊列中。
隊列=空

當隊列變空時,我們在這裡停止。

STEP 5:

返回高度,所以樹的高度是3。

推薦碼

用於查找二叉樹高度的迭代方法的Java代碼

import java.util.LinkedList;
import java.util.Queue;

class IterativeMethodToFindHeightOfBinaryTree {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static int height(Node root) {
        if (root == null) {
            return 0;
        }

        // create a queue and push root to it
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        // initialise height as 0
        int height = 0;

        // do a level order traversal
        // while queue is not empty
        while (!q.isEmpty()) {
            // increment height
            height++;
            // initialise size as size of queue
            int size = q.size();
            // Remove current level from queue and push next level
            for (int i = 0; i < size; i++) {
                // remove an element from queue
                Node curr = q.poll();
                // push current element's children to the queue
                if (curr.left != null)
                    q.add(curr.left);
                if (curr.right != null)
                    q.add(curr.right);
            }
        }
        
        // return height
        return height;
    }

    public static void main(String[] args) {
        // Example Tree 1
        Node root1 = new Node(2);
        root1.left = new Node(7);
        root1.right = new Node(11);
        root1.left.left = new Node(5);
        root1.right.left = new Node(9);
        root1.right.right = new Node(3);

        System.out.println(height(root1));

        // Example Tree 2
        Node root2 = new Node(1);
        root2.left = new Node(2);
        root2.right = new Node(3);
        root2.left.left = new Node(4);
        root2.left.right = new Node(5);
        root2.right.right = new Node(6);
        root2.left.left.left = new Node(7);
        root2.left.left.right = new Node(8);
        root2.right.right.left = new Node(9);
        root2.right.right.right = new Node(10);

        System.out.println(height(root2));
    }
}
3
4

用來找到二叉樹高度的迭代方法的C ++代碼

#include <bits/stdc++.h>
using namespace std;

// class representing node of a binary tree
class Node {
    public:
    int data;
    Node *left;     
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// function to create a new node with data d
Node* newNode(int d) {
    Node *node = new Node(d);
    return node;
}

int height(Node *root) {
    if (root == NULL) {
        return 0;
    }
    
    // create a queue and push root to it
    queue<Node*> q;
    q.push(root);
    // initialise height as 0
    int height = 0;
    
    // do a level order traversal
    // while queue is not empty
    while (!q.empty()) {
        // increment height
        height++;
        // initialise size as size of queue
        int size = q.size();
        // Remove current level from queue and push next level
        for (int i = 0; i < size; i++) {
            // remove an element from queue
            Node *curr = q.front();
            // push current element's children to the queue
            q.pop();
            if (curr->left != NULL)
                q.push(curr->left);
            if (curr->right != NULL)
                q.push(curr->right);
        }
    }
    
    // return height
    return height;
}

int main() {
    // Example Tree 1
    Node *root1 = newNode(2);
    root1->left = newNode(7);
    root1->right = newNode(11);
    root1->left->left = newNode(5);
    root1->right->left = newNode(9);
    root1->right->right = newNode(3);

    cout<<height(root1)<<endl;

    // Example Tree 2
    Node *root2 = newNode(1);
    root2->left = newNode(2);
    root2->right = newNode(3);
    root2->left->left = newNode(4);
    root2->left->right = newNode(5);
    root2->right->right = newNode(6);
    root2->left->left->left = newNode(7);
    root2->left->left->right = newNode(8);
    root2->right->right->left = newNode(9);
    root2->right->right->right = newNode(10);

    cout<<height(root2)<<endl;
    
    return 0;
}
3
4

複雜度分析

時間複雜度

O(N),其中n是二叉樹中的節點數。 由於我們使用了隊列並遍歷了二叉樹中的所有節點。 因此很明顯,時間複雜度是線性的。

空間複雜度

上), 其中n是二叉樹中的節點數。 如前所述,我們已經使用隊列來查找高度,我們已經將元素存儲在該隊列中。 因此,空間複雜度也是線性的。

參考