苦尽甘来时，一路向阳开
—— 24.10.21
104. 二叉树的最大深度
给定一个二叉树
root，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：3示例 2：
输入：root = [1,null,2] 输出：2输入：root = [3,9,20,null,null,15,7] 输出：3
方法1.深度优先搜索算法
思路
递归+后序遍历实现
① 得到左子树深度，得到右子树深度，二者最大者加一，就是本节点深度
② 因为需要先得到左右子树深度，很是然是后序遍历典型应用
③ 关于深度的定义:从根出发，离根最远的节点总边数
注意：力扣里的深度定义要多一
如果我们知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为左右子树的最大深度再加1，即max（l,r）+1
而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言，在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在 O(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;* }* }*/
class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;} else {int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return Math.max(leftHeight, rightHeight) + 1;}}
}
树1： 树2：
11 1
/ \ / \
7 11 1 4
/ \ / \
5 9 4 5
/ \ / \ / \
3 6 2 8 9 28
本地测试代码
public class LeetCode104BinaryTreeDepth {public static int maxDepth(TreeNode root){if (root == null) {return 0;} else {int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return Math.max(leftHeight, rightHeight) + 1;}}public static void main(String[] args) {TreeNode root1 = new TreeNode(11,new TreeNode(7,new TreeNode(5,new TreeNode(3),new TreeNode(6)),new TreeNode(9,new TreeNode(2),new TreeNode(8))),new TreeNode(11,new TreeNode(4,new TreeNode(9),new TreeNode(28)),new TreeNode(5)));TreeNode root2 = new TreeNode(1,new TreeNode(1),new TreeNode(4));System.out.println("root1_depth："+maxDepth(root1));System.out.println("root2_depth："+maxDepth(root2));}
}
方法2
非递归+后序遍历+栈实现
思路
代码
/*** 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 static int maxDepth(TreeNode root) {if (root == null) {return 0;}TreeNode cur = root;TreeNode pop = null;LinkedList<TreeNode> stack = new LinkedList<>();// 栈的最大高度int max = 0;while (cur != null || !stack.isEmpty()) {if (cur != null) {stack.push(cur);int size = stack.size();if (size > max) {max = size;}cur = cur.left;} else {TreeNode peek = stack.peek();if (peek.right == null || peek.right == pop) {pop = stack.pop();} else {cur = peek.right;}}}return max;}}
本地测试代码
import java.util.LinkedList;public class LeetCode104BinaryTreeDepth2 {public static int maxDepth(TreeNode root) {if (root == null) {return 0;}TreeNode cur = root;TreeNode pop = null;LinkedList<TreeNode> stack = new LinkedList<>();// 栈的最大高度int max = 0;while (cur != null || !stack.isEmpty()) {if (cur != null) {stack.push(cur);int size = stack.size();if (size > max) {max = size;}cur = cur.left;} else {TreeNode peek = stack.peek();if (peek.right == null || peek.right == pop) {pop = stack.pop();} else {cur = peek.right;}}}return max;}public static void main(String[] args) {TreeNode root1 = new TreeNode(11,new TreeNode(7,new TreeNode(5,new TreeNode(3),new TreeNode(6)),new TreeNode(9,new TreeNode(2),new TreeNode(8))),new TreeNode(11,new TreeNode(4,new TreeNode(9),new TreeNode(28)),new TreeNode(5)));TreeNode root2 = new TreeNode(1,new TreeNode(1), new TreeNode(4));System.out.println("root1_depth：" + maxDepth(root1));System.out.println("root2_depth：" + maxDepth(root2));}
}
方法3
思路
层序遍历法，最终遍历过几层，代表深度有多少
使用广度优先搜索（Breadth-First Search，BFS）的思想，通过一个队列来逐层遍历二叉树。每遍历完一层，深度加 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;* }* }*/
class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}// depth遍历统计树的深度int depth = 0;// Queue队列接口，实现类为链表LinkedList实现Queue<TreeNode> queue = new LinkedList<>();// 将二叉树加入队列中queue.offer(root);// int c1 = queue.size(); // 记录每层有几个元素// 通过每一层的结点数进行遍历完来判断每一层的分界线while (!queue.isEmpty()) {
// int c2 = 0; // 记录遍历时每一层的孩子数int size = queue.size();for (int i = 0; i < size; i++) {TreeNode poll = queue.poll(); // 根节点// 每次取出元素进行打印
// System.out.print(poll.value + " ");if (poll.left != null) { // 根节点的左孩子queue.offer(poll.left);
// c2++;}if (poll.right != null) { // 根节点的右孩子queue.offer(poll.right);
// c2++;}}
// c1 = c2;
// System.out.println();depth++;}return depth;}
}
本地测试代码
import java.util.LinkedList;
import java.util.Queue;public class LeetCode104BinaryTreeDepth3 {public int maxDepth(TreeNode root) {if (root == null) {return 0;}// depth遍历统计树的深度int depth = 0;// Queue队列接口，实现类为链表LinkedList实现Queue<TreeNode> queue = new LinkedList<>();// 将二叉树加入队列中queue.offer(root);// int c1 = queue.size(); // 记录每层有几个元素// 通过每一层的结点数进行遍历完来判断每一层的分界线while (!queue.isEmpty()) {
// int c2 = 0; // 记录遍历时每一层的孩子数int size = queue.size();for (int i = 0; i < size; i++) {TreeNode poll = queue.poll(); // 根节点// 每次取出元素进行打印
// System.out.print(poll.value + " ");if (poll.left != null) { // 根节点的左孩子queue.offer(poll.left);
// c2++;}if (poll.right != null) { // 根节点的右孩子queue.offer(poll.right);
// c2++;}}
// c1 = c2;
// System.out.println();depth++;}return depth;}public static void main(String[] args) {TreeNode root = new TreeNode(1,new TreeNode(2,new TreeNode(4),new TreeNode(5,new TreeNode(7), null)),new TreeNode(3,null,new TreeNode(6)));System.out.println(new LeetCode104BinaryTreeDepth3().maxDepth(root));}
}
![[AWS]RDS数据库版本升级](https://i-blog.csdnimg.cn/direct/4845146e528446038a65ffef6dc6a995.png)