题目描述

给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

题目分析

递归：左子树深度 和 右子树深度 中取最大值，再 + 1
迭代：使用队列存储结点，记录每层结点数，从而实现每层同时出队列，每出一层就让结果 + 1

Java

// 递归
public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

// 迭代
public int maxDepth2(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    int ans = 0;
    if (root == null) {
        return ans;
    }
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        while (size > 0) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            size--;
        }
        ans++;
    }
    return ans;
}

Kotlin

fun maxDepth(root: TreeNode?): Int {
    if (root == null) {
        return 0
    }
    return max(maxDepth(root.left), maxDepth(root.right)) + 1
}

fun maxDepth2(root: TreeNode?): Int {
    var ans = 0
    if (root == null) {
        return ans
    }
    val queue = LinkedList<TreeNode>()
    queue.offer(root)
    while (!queue.isEmpty()) {
        var size = queue.size
        while (size > 0) {
            val node = queue.poll()
            node.left?.let {
                queue.offer(it)
            }
            node.right?.let {
                queue.offer(it)
            }
            size--
        }
        ans++
    }
    return ans
}