Problem Description
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.
Input format
First line contains an integer n - Number of nodes.
Second line contains n space separated integers - The value of nodes.
Next n lines contain 3 space separated integers i, l, r describing left and right child of ith node as l and r respectively.
Output format
Print an integer - The length of the diameter.
Sample Input 1
8
10 15 25 12 40 16 8 9
1 5 3
5 6 -1
6 -1 7
7 -1 -1
3 2 4
2 8 -1
8 -1 -1
4 -1 -1
Sample Output 1
6
To solve the problem of finding the diameter of a binary tree, we can use a depth-first search (DFS) approach. The diameter of a binary tree is the length of the longest path between any two nodes, which can be determined by calculating the maximum path length for every node as a potential root of the longest path.
This implementation will still perform the task of calculating the diameter of the binary tree.
### C++ Implementation
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class BinaryTree {
public:
TreeNode* createTree(const vector<int>& values, const vector<pair<int, int>>& children, int index) {
if (index == -1) return nullptr;
TreeNode* node = new TreeNode(values[index - 1]);
node->left = createTree(values, children, children[index - 1].first);
node->right = createTree(values, children, children[index - 1].second);
return node;
}
int diameterOfBinaryTree(TreeNode* root) {
int diameter = 0;
height(root, diameter);
return diameter;
}
private:
//Recursion to calculate the height
int height(TreeNode* node, int& diameter) {
if (!node) return 0;
int leftHeight = height(node->left, diameter);
int rightHeight = height(node->right, diameter);
diameter = max(diameter, leftHeight + rightHeight); // Update the diameter
return max(leftHeight, rightHeight) + 1;
}
};
int main() {
int n;
cin >> n;
vector<int> values(n);
for (int i = 0; i < n; ++i) {
cin >> values[i];
}
vector<pair<int, int>> children(n);
for (int i = 0; i < n; ++i) {
int node, left, right;
cin >> node >> left >> right;
children[node - 1] = {left, right};
}
BinaryTree bt;
TreeNode* root = bt.createTree(values, children, 1);
cout << bt.diameterOfBinaryTree(root) << endl;
return 0;
}
```
### Explanation
1. **TreeNode Class**: The `TreeNode` class represents each node in the binary tree, with member variables `val`, `left`, and `right`.
2. **BinaryTree Class**:
- **createTree Function**: This member function of `BinaryTree` class constructs the binary tree from the input values and child indices.
- **diameterOfBinaryTree Function**: This member function initializes the diameter to 0 and calls the private `height` function to compute the diameter.
- **height Function**: This private member function calculates the height of the tree and updates the diameter during the traversal.
3. **main Function**:
- Reads the input values and constructs the binary tree using the `createTree` function of the `BinaryTree` class.
- Computes and prints the diameter using the `diameterOfBinaryTree` function.
### Input and Output
- **Input**: The first line contains the number of nodes `n`. The second line contains `n` space-separated integers representing the values of the nodes. The next `n` lines contain three integers each, representing the node index and its left and right children.
- **Output**: An integer representing the length of the diameter of the tree.
### Sample Input and Output
- **Sample Input**:
```
8
10 15 25 12 40 16 8 9
1 5 3
5 6 -1
6 -1 7
7 -1 -1
3 2 4
2 8 -1
8 -1 -1
4 -1 -1
```
- **Sample Output**:
```
6
```
Solution 2
Another implementation by declaring the diameter variable as global:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// Global variable to keep track of the diameter
int diameter;
// Function to create a tree from given input
TreeNode* createTree(const vector<int>& values, const vector<pair<int, int>>& children, int index) {
if (index == -1) return nullptr;
TreeNode* node = new TreeNode(values[index - 1]);
node->left = createTree(values, children, children[index - 1].first);
node->right = createTree(values, children, children[index - 1].second);
return node;
}
// Helper function to find the height of a tree and update the diameter
int height(TreeNode* node) {
if (!node) return 0;
int leftHeight = height(node->left);
int rightHeight = height(node->right);
diameter = max(diameter, leftHeight + rightHeight); // Update the diameter
return max(leftHeight, rightHeight) + 1;
}
// Function to find the diameter of the tree
int diameterOfBinaryTree(TreeNode* root) {
diameter = 0;
height(root);
return diameter;
}
int main() {
int n;
cin >> n;
vector<int> values(n);
for (int i = 0; i < n; ++i) {
cin >> values[i];
}
vector<pair<int, int>> children(n);
for (int i = 0; i < n; ++i) {
int node, left, right;
cin >> node >> left >> right;
children[node - 1] = {left, right};
}
TreeNode* root = createTree(values, children, 1);
cout << diameterOfBinaryTree(root) << endl;
// Clean up the allocated memory (optional, but good practice)
// Implement a tree deletion function if necessary
return 0;
}
No comments:
Post a Comment