Diameter of Binary Tree LeetCode solution in Java

1
class Solution {
2
  // Declare Global Variable ans to 0
3
  int ans = 0;
4

5
  // Depth First Search Function
6
  public int dfs(TreeNode root) {
7
    if (root == null) return 0;
8
    // recursive call for left height
9
    int lh = dfs(root.left);
10
    // recursive call for right height
11
    int rh = dfs(root.right);
12

13
    // update ans
14
    ans = Math.max(ans, lh + rh);
15

16
    // return max value
17
    return Math.max(lh, rh) + 1;
18
  }
19

20
  // Diameter of Binary Tree Function
21
  public int diameterOfBinaryTree(TreeNode root) {
22
    // Call dfs Function
23
    dfs(root);
24
    return ans;
25
  }
26
}
27

28
// Output -
29
/*
30
Input: root = [1,2,3,4,5]
31
Output: 3
32
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
33
*/
34

35
// Time & Space Complexity -
36
/*
37
Time - O(n)
38
Space - O(n)
39
*/