博客

二叉树的最大/最小深度

1.深度与高度

  • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
  • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）

　　根节点的高度就是二叉树的最大深度！！！

2.二叉树的最大深度

　　上面已经介绍了深度，所以我们这边求解最大深度只需要计算左右子树之中最大的深度+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;
    }
}

　　除了递归，我们还可以使用层序遍历进行求解，我们一层一层的遍历，直到遍历到最后一层，即可求出最大深度。

　　我们只需要在层序遍历代码里面加个变量计数即可，代码如下：

class solution {
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int depth = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.poll();
                if (node.left != null) {
                    deque.offer(node.left);
                }
                if (node.right != null) {
                    deque.offer(node.right);
                }
            }
        }
        return depth;
    }
}

3.二叉树的最小深度

　　刚刚做完最大深度，感觉最小深度也是一样，只需要将递归里面最大换成最小即可。

　　这就大错特错了，第一次我也犯了这个错，说到底就是最小深度是从根节点到最近叶子节点的最短路径上的节点数量。只有到了叶子节点才可以！！！所以这里我们多了几种情况进行判断。

      

       如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。 最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

　　根据思路我们可以得到以下代码：

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if (root.left == null) {
            return rightDepth + 1;
        }
        if (root.right == null) {
            return leftDepth + 1;
        }
        // 左右结点都不为null
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

　　同样我们也可以使用层次遍历求解，但是和上面不同，既然求最小，那么只要访问到了叶子节点就返回，就已经到了最小深度处，所以有如下代码：

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int depth = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode poll = deque.poll();
                if (poll.left == null && poll.right == null) {
                    // 是叶子结点，直接返回depth，因为从上往下遍历，所以该值就是最小值
                    return depth;
                }
                if (poll.left != null) {
                    deque.offer(poll.left);
                }
                if (poll.right != null) {
                    deque.offer(poll.right);
                }
            }
        }
        return depth;
    }
}

　　通过这两题又了解了二叉树，以后遇到类似的题目都不怕了！！！

　　不了解层序遍历的可以看我之前的博客 Here

4.LeetCode链接

　　最大深度：https://leetcode.cn/problems/maximum-depth-of-binary-tree/

　　最小深度：https://leetcode.cn/problems/minimum-depth-of-binary-tree/

Tags: