Skip to content

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: TreeNode | None) -> int:
    ans = 0

    def maxDepth(root: TreeNode | None) -> 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