代码随想录算法训练营第十六天|104.二叉树的最大深度 559.n叉树的最大深度 ● 111.二叉树的最小深度 ● 222.完全二叉树的节点个数
标签： 代码随想录算法训练营第十六天|104.二叉树的最大深度 559.n叉树的最大深度 ● 111.二叉树的最小深度 ● 222.完全二叉树的节点个数 Java博客 51CTO博客
2023-06-08 18:24:29 214浏览
104.二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例： 给定二叉树 [3,9,20,null,null,15,7]，
返回它的最大深度 3 。
思想：
递归法，第一步，返回值为int类型，输入元素为节点；第二步，终止条件是，遍历到根节点则返回；第三步，中间的逻辑是，前序后序或者中序遍历节点。
class Solution {
public int maxDepth(TreeNode root) {
return getDepth(root);
}
private int getDepth(TreeNode cur){
if(cur == null) return 0;
int left = getDepth(cur.left);
int right = getDepth(cur.right);
return 1+Math.max(left,right);
}
}559.n叉树的最大深度
给定一个 n 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
例如，给定一个 3叉树 :
我们应返回其最大深度，3。
思路：
和二叉树一致，只不过要考虑N叉树遍历写法
class Solution {
public int maxDepth(Node root) {
if(root == null) return 0;
int depth = 0;
if(root.children != null){
for(Node child : root.children){
depth = Math.max(depth, maxDepth(child));
}
}
return depth+1;
}
}111.二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
返回它的最小深度 2。
思路：
判断最小深度，需要注意必须是叶子节点，才算是深度的计算
class Solution {
public int minDepth(TreeNode root) {
return getDepth(root);
}
private int getDepth(TreeNode cur){
if(cur == null) return 0;
int leftDepth = getDepth(cur.left);
int rightDepth = getDepth(cur.right);
if(cur.left == null && cur.right != null){
return 1+rightDepth;
}
if(cur.left != null && cur.right == null){
return 1+leftDepth;
}
return 1 + Math.min(leftDepth, rightDepth);
}
}222.完全二叉树的节点个数
给出一个完全二叉树，求出该树的节点个数。
示例 1：
- 输入：root = [1,2,3,4,5,6]
- 输出：6
示例 2：
- 输入：root = []
- 输出：0
示例 3：
- 输入：root = [1]
- 输出：1
提示：
- 树中节点的数目范围是[0, 5 * 10^4]
- 0 <= Node.val <= 5 * 10^4
- 题目数据保证输入的树是 完全二叉树
思路：
递归的想法是，前序遍历，遇到空返回0，分别计算左右子树的节点数。
class Solution {
public int countNodes(TreeNode root) {
return count(root);
}
private int count(TreeNode cur){
if(cur == null) return 0;
int leftDe = count(cur.left);
int rightDe = count(cur.right);
return 1+leftDe+rightDe;
}
}好博客就要一起分享哦！分享海报
此处可发布评论
评论（0）展开评论
展开评论
