最大深度问题

二叉树的最大深度

二叉树深度和高度的区别

对于某个节点来说：

• 深度是指从根节点到该节点的最长简单路径边的条数；
• 高度是指从最下面的叶子节点到该节点的最长简单路径边的条数；

对于二叉树来说：

• 深度是从根节点数到它的叶节点；
• 高度是从叶节点数到它的根节点；

注意： 树的深度和高度一样，但是具体到树的某个节点，其深度和高度不一样。

题目描述

力扣链接🔗

递归法

后序遍历

求的根节点的高度，而根节点的高度就是这棵树的最大深度，所以才可以使用后序遍历。

1. 确定递归函数的参数和返回值
   参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。
2. 确定中止条件
   如果为空节点的话，就返回0，表示高度为0。
3. 确认单层递归的逻辑
   先求左孩子的深度，再求右孩子的深度，最后左右孩子中最大的深度再加上1（此节点）为此节点的最大深度。

/**
 * 递归法（后序）
*/
public int maxDepth(TreeNode root) {
    return getDepth(root);
}
public int getDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftDepth = getDepth(root.left);
    int rightDepth = getDepth(root.right);
    return 1 + Math.max(leftDepth, rightDepth); // 返回左右孩子最大的深度 + 本身节点
}

前序遍历

前序遍历是以深度的角度来求，所以没在一个节点都需要更新新的深度。

/**
 * 递归法（前序）
 *
 * @param root
 * @return
 */
int result = 0;
public int maxDepth(TreeNode root) {
    if (root == null) {
        return result;
    }
    getDepth(root, 1);
    return result;
}
public void getDepth(TreeNode root, int depth) {
    result = Math.max(result, depth);   // 此时处理为中节点，将最大的深度作为结果
    if (root.left == null && root.right == null) return; // 左右都为空，不需要处理左右孩子
    if (root.left != null) {
        depth++;
        getDepth(root.left, depth); // 左
        depth--;    // 到达最后一个节点，回溯
    }
    if (root.right != null) {
        depth++;
        getDepth(root.right, depth); // 右
        depth--;    // 到达最后一个节点，回溯
    }
    return;
}

迭代遍历

使用层序遍历模板，遍历一层加一即可。

/**
 * 使用层序遍历
 */
public int maxDepth(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    int deep = 0; // 深度
    if (root == null) {
        return 0;
    }
    queue.offer(root);
    while (!queue.isEmpty()) {
        int len = queue.size();
        while (len > 0) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
            len--;
        }
        deep++; // 深度加一
    }
    return deep;
}

N叉数的最大深度

与二叉树的最大深度思路一致

递归法

同样是求出子节点的最大深度，再加上一，为当前节点的最大深度，在进行递归。

/**
 * 递归遍历（后序）
 *
 * @param root
 * @return
 */
public int maxDepth(Node root) {
    if (root == null) {
        return 0;
    }
    int depth = 0;
    for (int i = 0; i < root.children.size(); i++) {
        depth = Math.max(depth, maxDepth(root.children.get(i)));    // 递归求出此节点的最大深度
    }
    return depth + 1;
}

迭代法

/**
* 层序遍历
*
* @param root
* @return
*/
public int maxDepth(Node root) {
    if (root == null) {
        return 0;
    }
    Queue<Node> queue = new LinkedList<>();
    int depth = 0;
    queue.offer(root);
    while (!queue.isEmpty()) {
        int len = queue.size();
        while (len > 0) {
            Node node = queue.poll();
            for (Node cilNode : node.children) {
                if (cilNode != null) queue.offer(cilNode);
            }
            len--;
        }
        depth++;
    }
    return depth;
}