Lowest Common Ancestor of Deepest Leaves LeetCode solution in C++

1
class Solution {
2
 public:
3
  int getDepth(TreeNode *root) {
4
    if (!root) return 0;
5
    return max(getDepth(root->right), getDepth(root->left)) + 1;
6
  }
7

8
  TreeNode *lcaDeepestLeaves(TreeNode *root) {
9
    if (!root) return NULL;
10

11
    int right_depth = getDepth(root->right);
12
    int left_depth = getDepth(root->left);
13

14
    if (right_depth == left_depth) return root;
15

16
    if (right_depth > left_depth)
17
      return lcaDeepestLeaves(root->right);
18

19
    else
20
      return lcaDeepestLeaves(root->left);
21
  }
22
};