苦尽甘来时，一路向阳开
—— 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));
}
}