第 08 关 | 二叉树的深度优先经典问题:2.白银挑战——二叉树的深度和高度问题-灵析社区
时光小少年今天我们来学习几道比较特别的题目——二叉树的深度和高度问题，这几道题对递归的考察要求更高一些，一起来看看
| 关卡名 | 二叉树的经典面试问题 | 我会了✔️ | |
|---|---|---|---|
| 内容 | 1. 最大深度问题 | ✔️ | |
| 2. 判断平衡树 | ✔️ | ||
| 3. 最小深度 | ✔️ | ||
| 4. N 叉树的最大深度 | ✔️ |
给定二叉树 [3,9,20,null,null,15,7]，如下图
3
/ \
9 20
/ \
15 7
然后LeetCode给我们造了一堆的题目，现在一起来研究一下104、110和111三个题，这三个题看起来挺像的，都是关于深度、高度的。
1. 最大深度问题
首先看一下104题最大深度:给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。例如上面的例子返回结果为最大深度为3。
我们先看一个简单情况：
3 3 3 3
/ \ / \ / \
9 20 9 20
对于node(3)，最大深度自然是左右子结点+1，左右子节点有的可能为空，只要有一个，树的最大高度就是1+1=2。然后再增加几个结点：
很显然相对于node(20)，最大深度自然是左右子结点+1，左右子节点有的可能为空，只要有一个，树的最大高度就是1+1=2，用代码表示就是：
int depth = 1 + max(leftDepth, rightDepth);
而对于3，则是左右子树深度最大的那个然后再+1，具体谁更大，则不必关心。所以对于node(3)的判断逻辑就是：
int leftDepth = getDepth(node.left); // 左
int rightDepth = getDepth(node.right); // 右
int depth = 1 + max(leftDepth, rightDepth); // 中
那什么时候结束呢，这里仍然是root == null返回0就行了。至于入参，自然是要处理的子树的根节点root，而返回值则是当前root所在子树的最大高度。所以合在一起就是：
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
int leftHight = maxDepth(root.left);
int rightHight = maxDepth(root.right);
return Math.max(leftHight,rightHight) + 1;
}
}
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
def maxDepth(self, root):
if root is None:
return 0
else:
left_height = self.maxDepth(root.left)
right_height = self.maxDepth(root.right)
return max(left_height, right_height) + 1
上面代码先拿到左右子树的结果再计算Math.max(left，right) + 1，这与后序遍历本质上一样的，因此可以看做后序遍历的拓展问题。
我们继续分析这个题，如果确定树最大有几层是不是也就知道最大深度了？ 是的，直接套用层序遍历的代码就可以。
具体做法是：我们修改2.2层次遍历中的分层方法，每获得一层增加一下技术就可以了。
/**
* 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 {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int ans = 0;
while (!queue.isEmpty()) {
//size表示某一层的所有元素数
int size = queue.size();
//size=0 表示一层访问完了
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;
}
}
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
queue<TreeNode*> Q;
Q.push(root);
int ans = 0;
while (!Q.empty()) {
int sz = Q.size();
while (sz > 0) {
TreeNode* node = Q.front();Q.pop();
if (node->left) Q.push(node->left);
if (node->right) Q.push(node->right);
sz -= 1;
}
ans += 1;
}
return ans;
}
def maxDepth(self, root: Optional[TreeNode]):
# 空树，高度为 0
if root == None:
return 0
# 初始化队列和层次
queue = [root]
depth = 0
# 当队列不为空
while queue:
# 当前层的节点数
n = len(queue)
# 弹出当前层的所有节点，并将所有子节点入队列
for i in range(n):
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
depth += 1
# 二叉树最大层次即为二叉树最深深度
return depth
2. 判断平衡树
LeetCode110 判断平衡二叉树：给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
这里的要求是二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。先补充一个问题，高度和深度怎么区分呢？
- 二叉树节点的深度:指从根节点到该节点的最⻓简单路径边的条数。
- 二叉树节点的高度:指从该节点到叶子节点的最⻓简单路径边的条数。
直接看图：
关于根节点的深度究竟是1 还是 0，不同的地方有不一样的标准，leetcode的题目中都是以根节点深度是1，其他的就不管了。
言归正传，我们仍然先看一个最简单的情况：
很显然只有两层的时候一定是平衡的，因为对于node(3)，左右孩子如果只有一个，那高度差就是1；如果左右子孩子都有或者都没有，则高度差为0。如果增加一层会怎么样呢？如下图：
对于node(3)，需要同时知道自己左右子树的最大高度差是否<2。
- 当节点root 左 / 右子树的高度差 < 2，则返回节点 root 的左右子树中最大高度加 1 （ max(left, right) + 1 ）；参考上面的高度和深度的对比图思考一下，这里为什么是最大高度？
- 当节点root 左 / 右子树的高度差 ≥2 ：则返回 -1 ，代表 此子树不是平衡树 。
也就是：
int left = recur(root.left);
int right = recur(root.right);
return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
我们此时就写出了核心递归。假如子树已经不平衡了，则不需要再递归了直接返回就行，比如这个树中结点4：
综合考虑几种情况 ，完整的代码如下：
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) >= 0;
}
public int height(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
return -1;
} else {
return Math.max(leftHeight, rightHeight) + 1;
}
}
}
int height( TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if (leftHeight == -1 || rightHeight == -1 || fabs(leftHeight - rightHeight) > 1) {
return -1;
} else {
return fmax(leftHeight, rightHeight) + 1;
}
}
bool isBalanced( TreeNode* root) {
return height(root) >= 0;
}
3. 最小深度
既然有最大深度，那是否有最小深度呢？LeetCode111就是：给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量，例如下面的例子返回结果为2。说明： 叶子节点是指没有子节点的节点。
前两个题都涉及最大深度，那将Max改成Min能不能解决本题呢？不行！注意下图:
这里的关键问题是题目中说的:最小深度是从根节点到最近叶子节点的最短路径上的节点数量，也就是最小深度的一层必须要有叶子结点，因此不能直接用。
这里的核心问题仍然是分析终止条件：
- 如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
- 反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。
最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。
代码如下：
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int min_depth = Integer.MAX_VALUE;
if (root.left != null) {
min_depth = Math.min(minDepth(root.left), min_depth);
}
if (root.right != null) {
min_depth = Math.min(minDepth(root.right), min_depth);
}
return min_depth + 1;
}
def minDepth(self, root) :
if not root:
return 0
if not root.left and not root.right:
return 1
min_depth = 10**9
if root.left:
min_depth = min(self.minDepth(root.left), min_depth)
if root.right:
min_depth = min(self.minDepth(root.right), min_depth)
return min_depth + 1
int minDepth(struct TreeNode *root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
int min_depth = INT_MAX;
if (root->left != NULL) {
min_depth = fmin(minDepth(root->left), min_depth);
}
if (root->right != NULL) {
min_depth = fmin(minDepth(root->right), min_depth);
}
return min_depth + 1;
}
除了递归方式 ，我们也可以使用层次遍历，只要遍历时，第一次遇到叶子就直接返回其所在的层次即可，改一下2.2中的方法即可。
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int minDepth = 0;
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (queue.size() > 0) {
//获取当前队列的长度，这个长度相当于 当前这一层的节点个数
int size = queue.size();
minDepth++;
for (int i = 0; i < size; ++i) {
TreeNode t = queue.remove();
if (t.left == null && t.right == null) {
return minDepth;
}
if (t.left != null) {
queue.add(t.left);
}
if (t.right != null) {
queue.add(t.right);
}
}
}
return 0;
}
4. N 叉树的最大深度
如果将二叉树换成N叉树又该怎么做呢？这就是LeetCode559.给定一个 N 叉树，找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
示例1：
输入：root = [1,null,3,2,4,null,5,6]
输出：3
示例2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：5
这道题就是将二叉树换成了N叉树，不同点就在于N叉树结点比较多，我们使用List存，遍历时用for即可，我们先看N叉树的定义：
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
}
这个题的实现和上一个题的最大区别就是处理子树时加了个处理List的for循环
public int maxDepth(Node root) {
if (root == null) {
return 0;
} else if (root.children.isEmpty()) {
return 1;
} else {
List<Integer> heights = new LinkedList<>();
for (Node item : root.children) {
heights.add(maxDepth(item));
}
return Collections.max(heights) + 1;
}
}
int maxDepth(Node* root) {
if (root == nullptr) {
return 0;
}
int maxChildDepth = 0;
vector<Node *> children = root->children;
for (auto child : children) {
int childDepth = maxDepth(child);
maxChildDepth = max(maxChildDepth, childDepth);
}
return maxChildDepth + 1;
}
def maxDepth(self, root) :
return max((self.maxDepth(child) for child in root.children), default=0) + 1 if root else 0
阅读量：306
点赞量：0
收藏量:0