104. Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: 3

Example 2:

Input: root = [1,null,2] Output: 2

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• -100 <= Node.val <= 100 104. Максимальная глубина двоичного дерева

Для заданного корня двоичного дерева вернуть его максимальную глубину.

Максимальная глубина двоичного дерева — это количество узлов на самом длинном пути от корневого узла до самого дальнего листового узла.

Пример 1:

Вход: root = [3,9,20,null,null,15,7] Выход: 3

Пример 2:

Вход: root = [1,null,2] Выход: 2

Ограничения:

• Количество узлов в дереве находится в диапазоне [0, 104].
• -100 <= Node.val <= 100

По сути максимальная глубина дерева это его высота, то есть можно использовать алгоритм поиска высоты - с помощью рекурсии и поиска в глубину. Создадим вспомогательную функцию dfs, которая будет вызываться рекурсивно для правого и левого деревьев. Если root равен null, то вернем 0, так как мы достигли листа, иначе рассчитаем высоту для левого и правого деревьев. В итоге вернем максимальную глубину правого либо левого дерева:

function maxDepth(root: TreeNode | null): number {
  return dfs(root);
}

function dfs(root: TreeNode | null): number {
  if (root === null) return 0;

  const left = dfs(root.left);
  const right = dfs(root.right);

  return Math.max(left, right) + 1;
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:

        def dfs(root: Optional[TreeNode]) -> int:
            if root == None:
                return 0

            left = dfs(root.left)
            right = dfs(root.right)

            return max(left, right) + 1

        return dfs(root)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
	depth := 0

	var dfs func(root *TreeNode) int

	dfs = func(root *TreeNode) int {
		if root != nil {
			left := dfs(root.Left)
			right := dfs(root.Right)
			d := max(left, right) + 1
			depth = max(depth, d)
			return d
		}

		return 0
	}

	dfs(root)

	return depth
}

func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int depth;

    private int dfs(TreeNode root) {
        if (root == null) return 0;

        int left = dfs(root.left);
        int right = dfs(root.right);
        int d = Math.max(left, right) + 1;

        depth = Math.max(depth, d);
        return d;
    }
    public int maxDepth(TreeNode root) {
        dfs(root);

        return depth;
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    int depth = 0;

    int dfs(TreeNode* root) {
        if (root) {
            int left = dfs(root->left);
            int right = dfs(root->right);
            int d = max(left, right) + 1;
            depth = max(depth, d);
            return d;
        }

        return 0;
    }
public:
    int maxDepth(TreeNode* root) {
        dfs(root);

        return depth;
    }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
    res := make([][]int, 0)
    bfs(root, 0, &res)
    return res
}

func bfs(root *TreeNode, level int, res *[][]int) {
    if root == nil {
        return
    }

    if len(*res) <= level {
        *res = append(*res, []int{})
    }

    (*res)[level] = append((*res)[level], root.Val)
    bfs(root.Left, level + 1, res)
    bfs(root.Right, level + 1, res)
}