数据结构
网络
关系数据库管理系统 (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 次浏览
广告