LeetCode Solutions
543. Diameter of Binary Tree
Time: $O(n)$ Space: $O(h)$
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int ans = 0;
maxDepth(root, ans);
return ans;
}
private:
int maxDepth(TreeNode* root, int& ans) {
if (root == nullptr)
return 0;
const int l = maxDepth(root->left, ans);
const int r = maxDepth(root->right, ans);
ans = max(ans, l + r);
return 1 + max(l, r);
}
};
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return ans;
}
private int ans = 0;
int maxDepth(TreeNode root) {
if (root == null)
return 0;
final int l = maxDepth(root.left);
final int r = maxDepth(root.right);
ans = Math.max(ans, l + r);
return 1 + Math.max(l, r);
}
}
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
ans = 0
def maxDepth(root: Optional[TreeNode]) -> int:
nonlocal ans
if not root:
return 0
l = maxDepth(root.left)
r = maxDepth(root.right)
ans = max(ans, l + r)
return 1 + max(l, r)
maxDepth(root)
return ans