資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學O(n)時間複雜度下二叉樹直徑的計算方法 [一種新方法] (C++)
二叉樹的直徑是每個節點的 (左子樹高度 + 右子樹高度 + 1)。因此，在這個方法中，我們將計算每個節點的 (左子樹高度 + 右子樹高度 + 1)，並更新結果。這裡的時間複雜度保持為 O(n)。
讓我們首先定義一個結構體來表示樹節點，它包含資料及其左右子節點。如果這是第一個建立的節點，那麼它是根節點，否則是子節點。
struct Node {
int data;
struct Node *leftChild, *rightChild;
};接下來，我們建立 `newNode(int data)` 函式，它接受一個整數值並將其賦值給節點的 data 成員。該函式返回指向已建立的 `Node` 結構體的指標。此外，新建立節點的左子節點和右子節點都設定為 null。
struct Node* newNode(int data){
struct Node* newNode = new Node;
newNode->data = data;
newNode->leftChild = newNode->rightChild = NULL;
return (newNode);
}`diameter(Node* root)` 函式接受根節點並檢查根節點是否為空。然後，我們用 `INT_MIN` 值定義 `ans` 變數。`height(root, ans)` 的返回值儲存到 `height_of_tree` 變數中。函式返回 `ans`。
int diameter(Node* root){
if (root == NULL)
return 0;
int ans = INT_MIN;
int height_of_tree = height(root, ans);
return ans;
}`height(Node* root, int& ans)` 函式接受根節點和 `ans` 變數（透過引用）。然後，我們對樹執行中序遍歷以計算其每個子樹的長度，並將 `ans` 的最大值作為第二個引數傳遞給每個遞迴呼叫。`ans` 是 (ans, 1 + 左子樹高度 + 右子樹高度) 的最大值。
示例
讓我們來看一下以下實現，它以 O(n) 的方法查詢二叉樹的直徑。
#include <iostream>
using namespace std;
struct Node {
int data;
Node* leftChild, *rightChild;
};
struct Node* newNode(int data){
struct Node* newNode = new Node;
newNode->data = data;
newNode->leftChild = newNode->rightChild = NULL;
return (newNode);
}
int height(Node* root, int& ans){
if (root == NULL)
return 0;
int left_height = height(root->left, ans);
int right_height = height(root->right, ans);
ans = max(ans, 1 + left_height + right_height);
return 1 + max(left_height, right_height);
}
int diameter(Node* root){
if (root == NULL)
return 0;
int ans = INT_MIN;
int height_of_tree = height(root, ans);
return ans;
}
int main(){
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Diameter is %d\n", diameter(root));
return 0;
}輸出
以上程式碼將產生以下輸出：
Diameter is 4
更新於：2021年1月16日
319 次瀏覽
廣告