西安做网站的网络公司,百度分析,网站设计的公司,东莞网站建设乐云seo文章目录 题目 104. 二叉树的最大深度题解后序遍历 递归实现后序遍历 迭代实现层序遍历 #x1f64a; 前言#xff1a;本文章为瑞_系列专栏之《刷题》的力扣LeetCode系列#xff0c;主要以力扣LeetCode网的题进行解析与分享。本文仅供大家交流、学习及研究使用#xff0c;禁… 文章目录 题目 104. 二叉树的最大深度题解后序遍历 递归实现后序遍历 迭代实现层序遍历 前言本文章为瑞_系列专栏之《刷题》的力扣LeetCode系列主要以力扣LeetCode网的题进行解析与分享。本文仅供大家交流、学习及研究使用禁止用于商业用途违者必究 题目 104. 二叉树的最大深度 原题链接104. 二叉树的最大深度 给定一个二叉树 root 返回其最大深度。 二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1 输入root [3,9,20,null,null,15,7] 输出3 示例 2 输入root [1,null,2] 输出2 提示
树中节点的数量在 [0, 104] 区间内。-100 Node.val 100
题解 关于二叉树的相关知识可以参考《瑞_数据结构与算法_二叉树》 二叉树的深度可以简单理解为层数如示例中3在1层20在2层7在3层
后序遍历 递归实现 思路1. 得到左子树深度, 得到右子树深度, 二者最大者加一, 就是本节点深度2. 因为需要先得到左右子树深度, 很显然是后序遍历典型应用3. 关于深度的定义从根(也可以是某节点)出发, 离根最远的节点总边数,注意: 力扣里的深度定义要多一深度2 深度3 深度11 1 1/ \ / \2 3 2 3\4/*** 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 node) {if (node null) {return 0;}int d1 maxDepth(node.left);int d2 maxDepth(node.right);return Integer.max(d1, d2) 1;}
}后序遍历 迭代实现 思路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) {TreeNode curr root;TreeNode pop null;LinkedListTreeNode stack new LinkedList();int max 0; // 栈的最大高度while (curr ! null || !stack.isEmpty()) {if (curr ! null) {stack.push(curr);// 只有往栈里push元素的时候高度才有可能变化int size stack.size();if (size max) {max size;}curr curr.left;} else {TreeNode peek stack.peek();if (peek.right null || peek.right pop) {pop stack.pop();} else {curr peek.right;}}}return max;}
}瑞在力扣上效率其实没有递归高 层序遍历 思路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;}QueueTreeNode queue new LinkedList();queue.offer(root);// 统计深度int depth 0;// 层序遍历while (!queue.isEmpty()) {int size queue.size();for (int i 0; i size; i) {TreeNode poll queue.poll();if (poll.left ! null) {queue.offer(poll.left);}if (poll.right ! null) {queue.offer(poll.right);}}depth ;}return depth;}
}本文是博主的粗浅理解可能存在一些错误或不完善之处如有遗漏或错误欢迎各位补充谢谢 如果觉得这篇文章对您有所帮助的话请动动小手点波关注你的点赞收藏⭐️转发评论都是对博主最好的支持~
