865. Smallest Subtree with all the Deepest Nodes

Version #1 DFS
Find the first node whose left subtree and right subtree have the same depth
Time Complexity is O(N)
-> 1st layer O(N)
-> 2nd layer O(N / 2)
-> 3rd layer O(N / 4)

100.00 %
class Solution {
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
if (root == null) return root;
TreeNode curr = root;
while (curr != null) {
int leftDepth = dfs(curr.left);
int rightDepth = dfs(curr.right);
if (leftDepth == rightDepth) {
return curr;
}
if (leftDepth < rightDepth) {
curr = curr.right;
} else {
curr = curr.left;
}
}
return curr;
}

private int dfs(TreeNode node) {
if (node == null) {
return 0;
}
return 1 + Math.max(dfs(node.left), dfs(node.right));
}
}