C++ 中二叉树直径的 O(n) [新方法]?
c++server side programmingprogramming
二叉树的直径是每个节点的 (left_height + right_height + 1)。因此，在此方法中，我们将计算每个节点的 (left_height + right_height + 1) 并更新结果。这里的时间复杂度保持为 O(n)。
让我们首先定义一个结构，该结构表示包含数据及其左节点和右节点子节点的树节点。如果这是要创建的第一个节点，则它是根节点，否则是子节点。
struct Node {
int data;
struct Node *leftChild, *rightChild;
};
接下来，我们创建 newNode(int data) 函数，该函数接受一个 int 值并将其分配给节点的数据成员。该函数返回指向创建的结构节点的指针。此外，新创建节点的左子节点和右子节点设置为 null。
struct Node* newNode(int data){
struct Node* newNode = new Node;
newNode->data = data;
newNode->leftChild = newNode->rightChild = NULL;
return (newNode);
}
diameter(Node* root) 函数接受根节点并检查根节点是否为 null。然后我们定义 ans 变量，值为 INT_MIN。 height(root, ans) 的返回值存储到 height_of_tree 变量中。ans 从函数返回。
intdiameter(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 的最大值在每次递归调用中作为第二个参数传递。答案是 (答案，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
