Самый левый элемент в последнем ярусе бинарного дерева

Дано не нулевое бинарное дерево (бинарное = в котором у каждой вершины не более двух детей), найти самый левый элемент в послднем ярусе дерева

Пример 1:

Дано:

    2
   / \
  1   3

Результат:
1

Пример 2:

Дано:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

Результат:
7

Идея решения

Обход дерева можно совершать в глубину или в ширину.

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

При обходе в ширину, мы рассматриваем весь ярус целиком и берем из него самую левую вершину.

Компилируемое решение DFS (поиск в глубину)

// две глобальные перемнные
int level = 0; // самый глубокий ярус дерева, который мы посетим
int leftMost; // результат

//  основная функцияpublic int findBottomLeftValue(TreeNode root) {
    //вырожденная ситуация: вместо дерева мы получили одну вершину 
    if (root.left == null && root.right == null) return root.val ;  
    
    // используем DFS-обход 
    dfs(root, level) ;   
    
    //возвращаем рузельтат после обхода
    return leftMost ; 
}
// вспомогательная DFS-функция
private void dfs(TreeNode root, int level) {
    if (root != null) {
    // текущий ярус глубже, чем те, что мы ранее посетили, 
    // и мы на нём впервые 
    // (потому что самый глубокий ярус дерева в переменной this.level)
    // то есть рассматриваем самый левый элемент,
    // поэтому обновляем самый левый элемент значением из текущей вершины
        if (level > this.level) { 
            this.level = level ; 
            leftMost = root.val ; 
        }
          
        // рекурсивно вызываем ярус, который + 1 ниже относительно текущего,
        // для левого поддерева.
        // Если этот ярус окажется глубже самого глубоко яруса, который
        // мы до сих пор посетили, то root.left будет самым левым элементом
        // данного яруса
        if (root.left != null) dfs(root.left, level + 1) ;
        
        // аналогично, для правого поддерева 
        if (root.right != null) dfs(root.right, level + 1) ; 
    }
} 

Компилируемое решение BFS (поиск в ширину)

public int findBottomLeftValue(TreeNode root) {
    // вырожденный случай 
    if (root.left == null && root.right == null) return root.val ;  
    
    Integer result = root.val;
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    q.add(root); // формируем очередь
    while(!q.isEmpty()) {
        int qsize = q.size(); // размер текущего яруса
 // удаляем весь текущий ярус (удаляем qsize элементов)
        for (int i = 0; i < qsize; i++) {
            TreeNode n = q.remove();
            if (i==0) { // самый левый элемент яруса
                result = n.val;
            }
     // добавляем в очередь элементы следующего яруса
            if (n.left!=null) {
                q.add(n.left);
            }
            if (n.right!=null) {
                q.add(n.right);
            }
        }
    }
    return result;
}