Максимальная высота дерева

Ссылка на leetcode: https://leetcode.com/problems/maximum-depth-of-binary-tree/description/

Задача. Дано бинарное дерево. Найти его максимальную высоту.

Например, для дерева

Ответ 4.

Решение. Будем использовать in-order алгоритм обхода бинарного дерева (Алгоритмы обхода двоичного дерева):

    public static void dfs(BinaryTree tree) {
      if (tree == null) {
        return;
      }
      visit(tree);
      dfs(tree.left);
      dfs(tree.right);
    }

Вариант 1 решения. Будем высоту считать снизу вверх. Когда достигли листовой вершины (нет дочерних верших), то вернем ноль. Для каждой вершины будем находить максимальную глубину между левой и правой подветкой и прибавлять 1 к результату.

    class Solution {
        public int maxDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }

Изобразил на картинке, для нашего примера как будут происходить вычисления. Для каждой вершины нарисовал красным, какие значения будет возвращать функция:

Вариант 2. Считаем высоту сверху вниз, высоту передаем в качестве параметра функции. Сохраняем результат в глобальной переменной.

    class Solution {
        int max = 0;
        public int maxDepth(TreeNode root) {
            //Высота корня дерева = 1
            traverse(root, 1);
            return max;
        }

        private void traverse(TreeNode root, int height) {
            if (root == null) {
                return;
            }
            //обновляем максимум
            max = Math.max(max, height);
            //рекурсивный вызов для левой и правой вершины
            traverse(root.left, height + 1);
            traverse(root.right, height + 1);
        }
    }

Вариант 3. Считаем высоту сверху вниз, высоту передаем в качестве параметра функции. Вычисляем максимальную глубину между левой и правой подветкой и возвращаем результат в качестве возвращаемого значения функции.

    class Solution {
        public int maxDepth(TreeNode root) {
            //Высота корня дерева = 1
            return dfs(root, 1);
        }

        private int dfs(TreeNode root, int height) {
            if (root == null) {
                return height - 1;
            }
            //рекурсивный вызов для левой и правой вершины
            int leftHeight = dfs(root.left, height + 1);
            int rightHeight = dfs(root.right, height + 1);

            return Math.max(leftHeight, rightHeight);
        }
    }