543 Diameter of Binary Tree¶
Given a binary tree, you need to compute 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.
Example: Given a binary tree
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Note: The length of path between two nodes is represented by the number of edges between them.
Idea:
Recursion
Solution 1:¶
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
ans_ = 0;
LP(root);
return ans_;
}
private:
int ans_;
int LP(TreeNode* root) {
if (!root) return -1;
int l = LP(root->left) + 1;
int r = LP(root->right) + 1;
ans_ = max(ans_, l + r);
return max(l, r);
}
};
Solution 2: passed 101/106 TLE - Floyd-Warshall¶
// State: 101/106 passed TLE
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
if (!root) return 0;
edges_.clear();
int n = 0;
buildGraph(root, n, -1);
vector<vector<int>> d(n, vector<int>(n, n));
for (int i = 0; i < n; ++i) d[i][i] = 0;
for (const auto& pair : edges_)
d[pair.first][pair.second] = 1;
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
int ans = INT_MIN;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
if (d[i][j] == n) continue;
ans = max(ans, d[i][j]);
}
return ans;
}
private:
void buildGraph(TreeNode* node, int& id, int pid) {
if (!node) return;
int node_id = id++;
if (pid >= 0) {
edges_.emplace_back(node_id, pid);
edges_.emplace_back(pid, node_id);
}
buildGraph(node->left, id, node_id);
buildGraph(node->right, id, node_id);
}
vector<pair<int,int>> edges_;
};
Solution 3:¶
Simulate recursion with a stack. We also need to track the return value of each node.
// Runtime: 15 ms
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
if (!root) return 0;
int ans = 0;
unordered_map<TreeNode*, int> d{{nullptr, -1}};
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* node = s.top();
if (d.count(node->left) && d.count(node->right)) {
int l = d[node->left] + 1;
int r = d[node->right] + 1;
ans = max(ans, l + r);
d[node] = max(l, r);
// children's results will never be used again, safe to delete here.
if (node->left) d.erase(node->left);
if (node->right) d.erase(node->right);
s.pop();
} else {
if (node->left) s.push(node->left);
if (node->right) s.push(node->right);
}
}
return ans;
}
};
Related Problems:¶
-
- Longest Univalue Path
-
- Network Delay Time