LeetCode Day16 104和amp;599和amp;111和amp;222
需要注意区别二叉树的深度和高度的区别,深度是指树从根结点到叶子节点走过的结点数,而高度是指树节点到叶子节点走过的结点数。深度是从上到下数的,而高度是从下往上数。 这题如果用递归法的话就很好做,可以递归求出这棵二叉树左子树最大深度和右子树最大深度,然后比较两边取最大值就是这个二叉树的最大深度了。
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
int right = maxDepth(root.right);
int left = maxDepth(root.left);
return Math.max(right, left) 1;
}
}
559. N 叉树的最大深度 这题如果用递归法解题和题104是相同的,解法如下:
//递归解法
class Solution {
public int maxDepth(Node root) {
if(root == null){
return 0;
}
int depth = 0;
if(root.children != null){
for(Node children : root.children){
depth = Math.max(depth, maxDepth(children));
}
}
return depth 1;
}
}
不难得知如果用层序遍历其实同样可以求出二叉树的最大深度,因为遍历了多少层,这个层数就是树深。所以还有一种迭代解法:
//迭代法题解
class Solution {
public int maxDepth(Node root) {
if(root == null) return 0;
int depth = 0;
Queue<Node> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
depth ;
int len = que.size();
while(len > 0){
Node node = que.poll();
for(int i = 0; i < node.children.size(); i ){
if(node.children.get(i) != null){
que.offer(node.children.get(i));
}
}
len --;
}
}
return depth;
}
}
111. 二叉树的最小深度 这题乍一看和104题一模一样只需要把比较最大值换成最小值就行了,但其实这样写的话ac不会通过,因为这个思路忽略了左子树或右子树全为空的情况,所以比较最小值之前需要给左右子树判空,那么这题的递归解法就出来了。
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){
return right 1;
}
if(root.right == null){
return left 1;
}
return Math.min(left, right) 1;
}
}
222. 完全二叉树的节点个数建议先补充了解完全二叉树的定义,然后递归法秒了。
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
//int res = 0;
int rightRes = countNodes(root.right);
int leftRes = countNodes(root.left);
return rightRes leftRes 1;
}
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgiifkh
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13