Нахождение наибольшей высоты бинарного дерева

Условие

Метод должен определить, насколько велика максимальная высота (глубина) заданного бинарного дерева, начиная с его корневого узла TreeNode root.

       4
      / \
     10  23
    /
   12
  /
 6

Ожидаемый результат для приведённого примера: 3.

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }
}

class TreeDepthFinder {
    public static int maxDepth(TreeNode root) {
        return 0; // TODO
    }
}

Ответ

По ожидаемому ответу высота считается в рёбрах: путь 4 → 10 → 12 → 6 имеет длину 3. Тогда высота листа равна 0, а пустого поддерева — −1.

public static int maxDepth(TreeNode root) {
    if (root == null) return -1;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Обход занимает O(n), рекурсивный стек — O(h). Название maxDepth иногда используют для числа узлов на пути: в такой договорённости пустое дерево имеет глубину 0, а пример дал бы 4. Здесь выбран именно контракт с ответом 3; соглашение для пустого дерева нужно явно зафиксировать. При большой глубине используйте итеративный обход.