算法通关村第八关|白银|二叉树的深度和高度问题【持续更新】

1.最大深度问题（后序遍历）

只需要一直递归，维护一个最大值。每一层只要有一个子节点，这个最大值就可以增加。

public int maxDepth(TreeNode root) {if (root == null) {return 0;}int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);// 这里要+1，不要漏掉root节点return Math.max(leftHeight, rightHeight) + 1;
}

2.最大深度问题（层次遍历）

遍历出多少层，那么最大深度就是多少。

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()) {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;
}

3.判断高度平衡二叉树

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。
二叉树的高度：从该节点到叶子节点的节点数。

public 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;}}
}

4.最小深度（递归）

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

是要有叶子节点才可以算最小深度的，所以当一个节点的一个子树为空，一个不为空的时候，要从不为空的子树继续算深度，不能直接返回结果。

public int minDepth(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}// 定义一个min_depth，比较left和right的大小（如果不为空的话）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;
}

5.最小深度（层次遍历）

找到第一个叶子节点即可。

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 node = queue.poll();// 先判断是不是叶子节点，是就直接返回值if (node.left == null && node.right == null) {return minDepth;}if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}}return 0;
}

6.N叉树的最大深度

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;}
}

N叉树的最大深度（递归）

用一个增强 for 循环遍历每个子树即可。

class Solution {public int maxDepth(Node root) {if (root == null) {return 0;} else if (root.children.isEmpty()) {return 1;} else {int max = 0;for (Node item : root.children) {int childrendepth = maxDepth(item);max = Math.max(max, childrendepth);}return max + 1;}}
}

N叉树的最大深度（层次遍历）

【持续更新】。

如果对您有帮助，请点赞关注支持我，谢谢！❤
如有错误或者不足之处，敬请指正！❤
个人主页：星不易 ❤
算法通关村专栏：不易|算法通关村 ❤