【深度优先】【广度优先】Leetcode 104 二叉树的最大深度 Leetcode 111 二叉树的最小深度 Leetcode 110 平衡二叉树
二叉树节点的深度：
指从根节点到该节点的最长简单路径边的条数或者节点数
（取决于深度从0开始还是从1开始）
二叉树节点的高度：
指从该节点到叶子节点的最长简单路径边的条数后者节点数
（取决于高度从0开始还是从1开始）
【前序求的是深度，后序求的是高度】
---------------🎈🎈题目链接🎈🎈-------------------
Leetcode 104 二叉树的最大深度
解法1 深度优先 递归法 后序：左右中
即先求左子树高度，再求右子树高度，再取最大返回给根节点
返回最大深度也就是求根节点的高度
时间复杂度O(N)
空间复杂度O(N)
java">/**
* 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)
java">
/**
* 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 111 二叉树的最小深度
---------------🎈🎈题目链接🎈🎈-------------------
解法1 深度优先：递归 后序遍历 左右中
这里要特别注意⭐️
最小深度—— 根节点到叶子节点的长度【左右孩子都为null的才是叶子结点】
/1.如果左子树为空，右子树不为空，最小深度是 1 + 右子树的深度。
/2.如果右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。
/3.如果左右子树都不为空，返回左右子树深度最小值 + 1 。
时间复杂度O(N)
空间复杂度O(N)
java">/**
* 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)
java">/**
* 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;
}
}
Leetcode 110 平衡二叉树
解法1 深度优先，求高度则用后序遍历：不断将左右子树的高度返回给根节点
1 明确递归函数的参数和返回值
参数：当前传入节点。 返回值：以当前传入节点为根节点的树的高度。
2 明确终止条件
递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0
3 明确单层递归的逻辑
如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢？当然是其左子树高度和其右子树高度的差值。
分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。
时间复杂度O(N)
空间复杂度O(N)
java">/**
* 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 boolean isBalanced(TreeNode root) {
int height = getHeight(root);
if(height != -1) return true;
else return false;
}
public int getHeight(TreeNode root){ // 参数和返回值
if(root == null) return 0; // 明确终止条件 递归的过程中遇到空节点终止，返回0，表示当前节点为根节点的树高度为0
int leftheight = getHeight(root.left); // left
if(leftheight == -1){
return -1;
}
int rightheight = getHeight(root.right); // right
if(rightheight == -1){
return -1;
}
if(Math.abs(leftheight-rightheight) >1) return -1; // root
else{return Math.max(leftheight,rightheight)+1;}
}
}
