# 543. Diameter of Binary Tree

• Time: $O(n)$
• Space: $O(h)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 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); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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