【深度优先】【广度优先】Leetcode 104 二叉树的最大深度
二叉树节点的深度：
指从根节点到该节点的最长简单路径边的条数或者节点数
（取决于深度从0开始还是从1开始）
二叉树节点的高度：
指从该节点到叶子节点的最长简单路径边的条数后者节点数
（取决于高度从0开始还是从1开始）
【前序求的是深度，后序求的是高度】
---------------🎈🎈题目链接🎈🎈-------------------
Leetcode 104 二叉树的最大深度
解法1 深度优先 递归法 后序：左右中
即先求左子树高度，再求右子树高度，再取最大返回给根节点
返回最大深度也就是求根节点的高度
时间复杂度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 maxDepth(TreeNode root) {
// 返回最大深度也就是求根节点的高度
// 采用深度优先 递归法 后序：左右中 即先求左子树高度，再求右子树高度，再取最大返回给根节点
if(root == null) return 0;
// 左
int leftdepth = maxDepth(root.left);
// 右
int rightdepth = maxDepth(root.right);
// 中
return 1 + Math.max(leftdepth,rightdepth);
}
}
解法2 广度优先：层序遍历
时间复杂度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 maxDepth(TreeNode root) {
// 层序遍历
Queue<TreeNode> myqueue = new LinkedList<>();
if(root == null) return 0;
myqueue.add(root);
int result = 0;
while(!myqueue.isEmpty()){
int size = myqueue.size();
for(int i = 0; i < size; i++){
TreeNode temp = myqueue.poll();
if(temp.left != null){
myqueue.add(temp.left);
}
if(temp.right != null){
myqueue.add(temp.right);
}
}
result +=1;
}
return result;
}
}
Leetcode 110 二叉树的最小深度
---------------🎈🎈题目链接🎈🎈-------------------
解法1 深度优先：递归 后序遍历 左右中
这里要特别注意⭐️
最小深度—— 根节点到叶子节点的长度【左右孩子都为null的才是叶子结点】
/1.如果左子树为空，右子树不为空，最小深度是 1 + 右子树的深度。
/2.如果右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。
/3.如果左右子树都不为空，返回左右子树深度最小值 + 1 。
时间复杂度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 minDepth(TreeNode root) {
// 深度优先遍历 递归 后序遍历 左右中
// 最小深度—— 根节点到叶子节点的长度【左右孩子都为null的才是叶子结点】
// 1.如果左子树为空，右子树不为空，最小深度是 1 + 右子树的深度。
// 2.如果右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。
// 3.如果左右子树都不为空，返回左右子树深度最小值 + 1 。
if(root == null) return 0; //递归终止条件，遇到null返回0，表示当前的节点的高度为0
int leftdepth = minDepth(root.left); // 左
int rightdepth = minDepth(root.right); // 右
if(root.left == null){
return 1+rightdepth;}
else if(root.right == null){
return 1+leftdepth;}
else{
return 1+Math.min(leftdepth,rightdepth);
}
}
}
解法2 广度优先：层序遍历
时间复杂度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 minDepth(TreeNode root) {
// 层序遍历
Queue<TreeNode> myqueue = new LinkedList<>();
if(root == null) return 0;
myqueue.add(root);
int result = 0;
while(!myqueue.isEmpty()){
int size = myqueue.size();
for(int i = 0; i < size; i++){
TreeNode temp = myqueue.poll();
if(temp.left != null){
myqueue.add(temp.left);
}
if(temp.right != null){
myqueue.add(temp.right);
}
if(temp.left == null && temp.right==null){
return result+1;
}
}
result +=1;
}
return result;
}
}
