代码随香录算法训练营day16 | 104. 二叉树的最大深度,559. N 叉树的最大深度,111. 二叉树的最小深度,222. 完全二叉树的节点个数

news/2024/10/31 7:34:45/

目录

104. 二叉树的最大深度

559. N 叉树的最大深度

111. 二叉树的最小深度

222. 完全二叉树的节点个数


104. 二叉树的最大深度

学了回溯之后再来做一下

思路:

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

dfs,bfs,迭代三个方法都可以做这道题;

 代码:

//  dfs
class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}int leftMax = maxDepth(root.left);int rightMax = maxDepth(root.right);return Math.max(leftMax, rightMax) + 1;}
}// bfs
class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int depth = 0;while (!queue.isEmpty()) {int len = queue.size();for (int i = 0; i < len; i++) {TreeNode node = queue.poll();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}depth++;}return depth;}
}class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}// 不影响if (root.left == null && root.right == null) {return 1;}int l = maxDepth(root.left);int r = maxDepth(root.right);return Math.max(l, r) + 1;}
}

559. N 叉树的最大深度

 代码:

/*
// Definition for a Node.
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;}
};
*/class Solution {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;}
}

111. 二叉树的最小深度

思路:

        叶子节点是指左右节点都为空的情况,不能直接比较左右子树的最小深度,需要加以限制。例如[1, null, 2],的最小深度为2,但如果直接取左右最小深度则容易算成1。

·        所以需要分情况:如果左子树为空,则最小深度为右子树最小深度+1;如果右子树为空,最小深度为左子树最小深度+1。左右子树都不为空,再去二者较小的深度+1;

代码:

/*** 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;*     }* }*///  dfs
// 叶子节点是指左右孩子都为空的节点
class Solution {public int minDepth(TreeNode root) {if (root == null) {return 0;}int left = minDepth(root.left);int right = minDepth(root.right);// 左右孩子都为空if (root.left == null && root.right == null) {return 1;}// 只有左孩子为空if (root.left == null) {return right + 1;} // 只有右孩子为空if (root.right == null) {return left + 1;}// 左右孩子都不为空return Math.min(left, right) + 1;}
}// bfs
class Solution {public int minDepth(TreeNode root) {if (root == null) {return 0;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int minD = 0;while (!queue.isEmpty()) {int len = queue.size();minD++;for (int i = 0; i < len; i++) {TreeNode node = queue.poll();// 层序遍历,左右节点为空说明是叶子节点,第一个叶子节点对应最小深度if (node.left == null && node.right == null) {return minD;}if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}return minD;}
}

222. 完全二叉树的节点个数

思路:

        愉快的简单题。

代码: 

// dfs
class Solution {public int countNodes(TreeNode root) {if (root == null) {return 0;}return countNodes(root.left) + countNodes(root.right) + 1;}
}class Solution {public int countNodes(TreeNode root) {return root == null? 0: countNodes(root.left) + countNodes(root.right) + 1;}
}// 迭代前序
class Solution {public int countNodes(TreeNode root) {int count = 0;if (root == null) {return count;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();count++;if (node.right != null) {stack.push(node.right);}if (node.left != null) {stack.push(node.left);}}      return count;}
}


http://www.ppmy.cn/news/991352.html

相关文章

C语言的链表操作

C语言中可以使用结构体和指针实现链表操作。链表是一种动态数据结构,由节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针。以下是一个简单的示例: #include <stdio.h> #include <stdlib.h>// 定义链表节点结构体 struct Node {int data;struct No…

java外观模式

在Java中&#xff0c;外观模式&#xff08;Facade Design Pattern&#xff09;用于为复杂的子系统提供一个简单的接口&#xff0c;以方便客户端的使用。外观模式是一种结构型设计模式&#xff0c;它隐藏了系统的复杂性&#xff0c;将多个类的复杂操作封装在一个外观类中&#x…

用C语言实现堆排序算法

1.设计思路 排序的思想将一个数组按递增的顺序进行排序&#xff0c;将数组的第一个位置空下&#xff08;下标为0&#xff09;&#xff0c;因为会导致子节点和本身同一个结点&#xff08;i和2i一致&#xff09;&#xff0c;每次堆排序在下标1的位置放上了最大值&#xff0c;然后…

使用 GORM 连接数据库并实现增删改查操作

步骤 1&#xff1a;安装 GORM 首先&#xff0c;我们需要安装 GORM 包。在终端中运行以下命令&#xff1a; shell go get -u gorm.io/gorm 步骤 2&#xff1a;导入所需的包 在 Go 代码的开头导入以下包&#xff1a; import ("gorm.io/driver/mysql" // 如果你使用…

腾讯云高性能计算集群CPU服务器处理器说明

腾讯云高性能计算集群以裸金属云服务器为节点&#xff0c;通过RDMA互联&#xff0c;提供了高带宽和极低延迟的网络服务&#xff0c;能满足大规模高性能计算、人工智能、大数据推荐等应用的并行计算需求&#xff0c;腾讯云服务器网分享腾讯云服务器高性能计算集群CPU处理器说明&…

GoogleLeNet V2 V3 —— Batch Normalization

文章目录 Batch Normalizationinternal covariate shift激活层的作用BN执行的位置数据白化网络中的BN层训练过程 BN的实验效果MNIST与GoogleLeNet V1比较 GoogleLeNet出来之后&#xff0c;Google在这个基础上又演进了几个版本&#xff0c;一般来说是说有4个版本&#xff0c;之前…

selenium的三种等待方式(强制等待,隐式等待,显示等待)

目录 1.强制等待&#xff08;无条件等待&#xff09; 2.隐式等待 3.显示等待 有时候做自动化测试&#xff0c;需要进行等待&#xff0c;因为下一步的操作依赖于上一步的结果&#xff0c;但是程序执行的很快&#xff0c;有时候页面还未加载完成就进行了下一步的操作&#xff…

Python运算符列表及其优先顺序、结合性

本文表格对Python中运算符的优先顺序进行了总结&#xff0c;从最高优先级&#xff08;最先绑定&#xff09;到最低优先级&#xff08;最后绑定&#xff09;。相同单元格内的运算符具有相同优先级。除非句法显式地给出&#xff0c;否则运算符均指二元运算。 相同单元格内的运算…