首页 > 其他分享 >04.二叉树的最大深度 (优先掌握递归)111.二叉树的最小深度 (优先掌握递归) 222.完全二叉树的节点个数(优先掌握递归)

04.二叉树的最大深度 (优先掌握递归)111.二叉树的最小深度 (优先掌握递归) 222.完全二叉树的节点个数(优先掌握递归)

时间:2023-02-04 11:37:09浏览次数:51  
标签:优先 right TreeNode val 递归 int 二叉树 root left


04.二叉树的最大深度

04.二叉树的最大深度 (优先掌握递归)111.二叉树的最小深度 (优先掌握递归) 222.完全二叉树的节点个数(优先掌握递归)_深度优先

/**
* 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) {

int a = dfs(root);
return a;
}
int dfs(TreeNode root){
if (root == null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
return Math.max(left,right) + 1;
}
}

04.二叉树的最大深度 (优先掌握递归)111.二叉树的最小深度 (优先掌握递归) 222.完全二叉树的节点个数(优先掌握递归)_深度优先_02

111.二叉树的最小深度

04.二叉树的最大深度 (优先掌握递归)111.二叉树的最小深度 (优先掌握递归) 222.完全二叉树的节点个数(优先掌握递归)_深度优先_03

/**
* 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 minDepth(TreeNode root) {
int a = dfs(root);
return a;
}
public int dfs(TreeNode root){
if(root == null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
if(root.left != null && root.right == null){
return left + 1;
}
if(root.left == null && root.right != null){
return right + 1;
}
int result = Math.min(left,right)+1;
return result;
}

}

04.二叉树的最大深度 (优先掌握递归)111.二叉树的最小深度 (优先掌握递归) 222.完全二叉树的节点个数(优先掌握递归)_空间复杂度_04

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

04.二叉树的最大深度 (优先掌握递归)111.二叉树的最小深度 (优先掌握递归) 222.完全二叉树的节点个数(优先掌握递归)_空间复杂度_05

采用层次遍历:
时间复杂度O(n)
空间复杂度O(n)

/**
* 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 countNodes(TreeNode root) {
if(root == null) return 0;
Queue<TreeNode> queue= new LinkedList<>();
queue.offer(root);
int nums = 0;
while(!queue.isEmpty()){
int len = queue.size();
nums += len;
while(len > 0){
TreeNode temp = queue.poll();
if(temp.left != null) queue.add(temp.left);
if(temp.right != null) queue.add(temp.right);
len--;
}
}
return nums;
}
}

04.二叉树的最大深度 (优先掌握递归)111.二叉树的最小深度 (优先掌握递归) 222.完全二叉树的节点个数(优先掌握递归)_算法_06


如果采用上一种方法,没有使用完全二叉树的条件不太合理。

普通递归法:

/**
* 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 countNodes(TreeNode root) {
int result = f(root);
return result;
}
int f(TreeNode root){
if(root == null) return 0;
return f(root.left) + f(root.right) + 1;
}
}

04.二叉树的最大深度 (优先掌握递归)111.二叉树的最小深度 (优先掌握递归) 222.完全二叉树的节点个数(优先掌握递归)_空间复杂度_07


利用完全二叉树的规律:

时间复杂度(lgn * lgn)

空间复杂度(lgn)

04.二叉树的最大深度 (优先掌握递归)111.二叉树的最小深度 (优先掌握递归) 222.完全二叉树的节点个数(优先掌握递归)_leetcode_08

/**
* 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 countNodes(TreeNode root) {
int result = f(root);
return result;
}
int f(TreeNode root){
if(root == null) return 0;
TreeNode left = root.left;
TreeNode right = root.right;
int depthleft = 0,depthright = 0;
while(left != null){
left = left.left;
depthleft++;
}
while(right != null){
right = right.right;
depthright++;
}
if(depthleft == depthright){
return (2 << depthleft) - 1;
}
return f(root.left) + f(root.right) + 1;
}
}

04.二叉树的最大深度 (优先掌握递归)111.二叉树的最小深度 (优先掌握递归) 222.完全二叉树的节点个数(优先掌握递归)_完全二叉树_09


标签:优先,right,TreeNode,val,递归,int,二叉树,root,left
From: https://blog.51cto.com/u_15911055/6036991

相关文章

  • 226. 翻转二叉树 101. 对称二叉树
    226.翻转二叉树dfs:/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode()......
  • 二叉树的层次遍历
    文章目录​​二叉树的层次遍历​​​​二叉树的层次遍历​​​​107.二叉树的层序遍历II​​​​199.二叉树的右视图​​​​637.二叉树的层平均值​​​​429.N叉树的......
  • 二叉树
    二叉树二叉树的概念二叉树是n(n≥0)个结点的有限集或者是空集(n=O),或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成二叉树结构最简单......
  • 递归-分治
    递归递归,将问题分解为重叠的子问题,f(n)=f(n-1)+xxx,满足这样的状态转移方程,说明原问题是不是依赖递归子问题,即f(n)依赖f(n-1)确定递归出口递归返回时还原现场78.子......
  • 代码随想录算法训练营第十七天 | 110.平衡二叉树,257. 二叉树的所有路径,404.左叶子之和
    一、昨日回顾与补充今天看了Day16讲解的视频,对于求二叉树最大深度、最小深度以及求完全二叉树的节点个数有了新的理解,总结如下:1.深度和高度的区别(之前就看看定义忽略......
  • 由逗号、赋值优先级想到的语法结构
    逗号的意义在C语言中,逗号用来表示一个中间的表达式;而在lua和Python中,逗号通常用来作为多值赋值的一种语法。这就导致一个有意思的现象,相同的语句在C/LUA语言中不同的意义......
  • #yyds干货盘点# LeetCode程序员面试金典: 递归乘法
    题目:递归乘法。写一个递归函数,不使用*运算符,实现两个正整数的相乘。可以使用加号、减号、位移,但要吝啬一些。示例1:输入:A=1,B=10输出:10示例2:输入:A=3,B=4......
  • 万字详解递归与递推
    前言相信这个故事,朋友们应该都不陌生,从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?「从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事......
  • leetcode-二叉树展开为链表
    //leetcodesubmitregionbegin(Prohibitmodificationanddeletion)/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;......
  • BM35 判断是不是完全二叉树
    思路:判断一个二叉树是不是完全二叉树,先弄清楚二叉树的定义,只有最后一层和倒数第一层有叶子结点,也就是说当访问到空节点时,后面不应该再有节点可访问了。即空节点一定是在......