Problem:
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
|
1 2 3 4 5 |
1 / \ 2 3 / \ 4 5 |
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
Solution1:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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
C++ / Floyd-Warshall
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
// Author: Huahua // 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.
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
""" Author: Huahua Runtime: 82 ms """ class Solution: def diameterOfBinaryTree(self, root): if not root: return 0 d = {None: -1} s = [root] ans = 0 while s: node = s[-1] if node.left in d and node.right in d: s.pop() l = d[node.left] + 1 r = d[node.right] + 1 ans = max(ans, l + r) d[node] = max(l, r) else: if node.left: s.append(node.left) if node.right: s.append(node.right) return ans |
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua // 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:
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment