天道酬勤,学无止境

【LeetCode刷题(简单程度)】剑指 Offer 55 - I. 二叉树的深度

输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。

例如:

给定二叉树 [3,9,20,null,null,15,7],
在这里插入图片描述
返回它的最大深度 3 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路1:常规方法,利用层次遍历。该层遍历完深度就加`1。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        return travelevel(root);
    }

    int travelevel(TreeNode* root)
    {
        int depth = 0;
        if(!root)
            return 0;
        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty())
        {
            int size = q.size();
            for(int i = 0;i < size;++i)
            {
                TreeNode* cur = q.front();
                q.pop();
                if(cur->left)
                    q.push(cur->left);
                if(cur->right)
                    q.push(cur->right);
            }
            depth++;
        }
        return depth;
    }
};

思路2:一棵树的深度应该是其左右子树深度较大的值,一棵数如果只有一个节点那么深度是1,如果只有左孩子,那么深度为其左子树深度加1(1为加上当前节点),右子树同理。所以可以采用递归。代码实现如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root)
            return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);

        return (left > right) ? left + 1: right + 1;
    }
};

受限制的 HTML

  • 允许的HTML标签:<a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • 自动断行和分段。
  • 网页和电子邮件地址自动转换为链接。

相关推荐
  • LeetCode+剑指offer 题目(按标签汇总)
    前言 所用语言:c++ 。题号用 “剑指XX” 表示的都是剑指上的题,其余都是LeetCode上的题。 计划刷题,3遍以上。 其中,剑指除1题、2题之外,其余全部完整(共66道,3~68)。 2020.02.15 一刷; 2020.04.05 二刷。 该LeedCode笔记参照了下面优秀的博主笔记,并按照他们整理的高频题目来刷的,在此感谢。 博主笔记链接: https://blog.csdn.net/kk55guang2/article/details/85223256 https://www.cnblogs.com/grandyang/p/4606334.html 页面跳转的方法(即,点击题目可跳转到相应题目解答): [点击跳转](https://blog.csdn.net/weixin_43330388/article/details/104331278/#jump) [开始跳](#jump) 文章内容... <span id="jump">跳到这</span> 数组相关(剑指11道) (1)LC 01.两数之和 (2)LC 167 两数之和||-输入有序数组 (3)LC 15.三数之和 (4)LC 16.最接近的三数之和 (5)LC 18.四数之和 (6)LC 217.存在重复元素 (7)LC 26. 删除排序数组中的重复项 (8)LC 80. 删除排序数组中的重复项 II
  • Leetcode、剑指offer、笔试题刷题清单
    Leetcode、剑指offer、笔试题刷题清单 一、剑指offer1、数据结构1.1 树与二叉树1.2 栈与队列1.3 数组(查找与排序)1.4 链表1.5 字符串 2.算法2.1 动态规划与贪婪(递归与循环)2.2 查找与排序2.3 回溯法2.4 位运算2.5 数学 Leetcode高频题100二、LeetCode高频题目分类Hash相关链表操作双指针遍历/滑动窗口快慢指针遍历区间合并字符串操作数字操作数组操作栈相关堆相关递归分治法/二分法动态规划回溯法树的遍历二叉搜索树相关 三、 Leetcode玩转算法第一天 数组问题第二天 查找表问题第三天 链表问题第四天 二叉树与递归第五天 栈,队列,优先队列第六天 递归回溯问题第七天 动态规划问题第八天 贪心算法 四、笔试面试题面试题小米实习面试快手面试字节面试汇总 笔试题Bilibili笔试招行网络科技爱奇艺笔试题小米海康威视京东笔试字节实习面经其他字节跳动笔试题 一、剑指offer 1、数据结构 1.1 树与二叉树 面试题7:重建二叉树 面试题8:二叉树的下一个节点 面试题26:树的子结构 面试题27:二叉树的镜像 面试题28:对称的二叉树 面试题29:顺时针打印矩阵 面试题32:从上到下打印二叉树 面试题33:二叉搜索树的后序遍历序列 面试题34:二叉树中和为某一值的路径 面试题36:二叉搜索树与双向链表 面试题37
  • leetcode分类整理
    剑指offer 剑指 Offer 03. 数组中重复的数字 剑指 Offer 04. 二维数组中的查找 剑指 Offer 05. 替换空格 剑指 Offer 06. 从尾到头打印链表 剑指 Offer 07. 重建二叉树 剑指 Offer 09. 用两个栈实现队列 剑指 Offer 10- I. 斐波那契数列 剑指 Offer 10- II. 青蛙跳台阶问题 剑指 Offer 11. 旋转数组的最小数字 剑指 Offer 12. 矩阵中的路径 剑指 Offer 13. 机器人的运动范围 剑指 Offer 14- I. 剪绳子 剑指 Offer 14- II. 剪绳子 II 剑指 Offer 15. 二进制中1的个数 剑指 Offer 16. 数值的整数次方 剑指 Offer 17. 打印从1到最大的n位数 剑指 Offer 18. 删除链表的节点 剑指 Offer 19. 正则表达式匹配 - 待完成 剑指 Offer 20. 表示数值的字符串 - 待完成 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 剑指 Offer 22. 链表中倒数第k个节点 剑指 Offer 24. 反转链表 剑指 Offer 25. 合并两个排序的链表 剑指 Offer 26. 树的子结构 剑指 Offer 27. 二叉树的镜像 剑指 Offer 28. 对称的二叉树 剑指 Offer 29
  • Leetcode刷题:剑指offer【面试题55-Ⅰ 二叉树的深度】
    【面试题55-Ⅰ 二叉树的深度】 输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。 Leetcode题目对应位置: 面试题55-Ⅰ:二叉树的深度 思路 1:树的深度优先遍历,采用递归实现。树的高度 = max(左子树深度,右子树深度) + 1。 递归终止条件:当 root 为空时,返回树深度为 0递归过程:计算 root 左子树的深度,计算 root 右子树的深度返回值:树的深度 时间复杂度: O ( n ) O(n) O(n),n 为树的节点数量,遍历所有节点 空间复杂度: O ( n ) O(n) O(n),最坏情况下,树退化为链表,递归深度为 n class Solution: def maxDepth(self, root: TreeNode) -> int: if not root: return 0 return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1 思路 2:树的广度优先遍历,基于队列实现。每遍历完一层树的高度就 + 1。 循环终止条件:队列为空时跳出循环过程:遍历队列中的节点,并将其左子节点和右子节点放在辅助列表中,遍历完队列的所有节点后,将辅助列表赋值给队列,即将下一层节点赋值给了队列,此时执行层数 +
  • LeetCode刷题记录
    LeetCode刷题记录 开始佛系刷题。。。 剑指Offer系列 题目链接题解备注剑指 Offer 03. 数组中重复的数字传送门哈希表用法剑指 Offer 04. 二维数组中的查找传送门数组简单用法剑指 Offer 05. 替换空格传送门字符串简单用法剑指 Offer 06. 从尾到头打印链表传送门数组简单用法剑指 Offer 07. 重建二叉树传送门中序前序建树剑指 Offer 09. 用两个栈实现队列传送门栈模仿队列剑指 Offer 10- I. 斐波那契数列传送门斐波拉契数列剑指 Offer 10- II. 青蛙跳台阶问题传送门斐波拉契数列变种剑指 Offer 11. 旋转数组的最小数字传送门二分查找剑指 Offer 12. 矩阵中的路径传送门DFS剑指 Offer 13. 机器人的运动范围传送门DFS&BFS&DP剑指 Offer 14- I. 剪绳子传送门算术几何不等式剑指 Offer 14- II. 剪绳子 II传送门快速幂剑指 Offer 15. 二进制中1的个数传送门二进制剑指 Offer 16. 数值的整数次方传送门快速幂剑指 Offer 17. 打印从1到最大的n位数传送门打印大数,字符串,DFS剑指 Offer 18. 删除链表的节点传送门链表剑指 Offer 21. 调整数组顺序使奇数位于偶数前面传送门快排剑指 Offer 22
  • 剑指 Offer 55 - II. 平衡二叉树 - leetcode 剑指offer系列
    题目难度: 简单 原题链接 今天继续更新剑指 offer 系列, 老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了 题目描述 输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过 1,那么它就是一棵平衡二叉树。 1 <= 树的结点个数 <= 10000 题目样例 示例 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。 给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4 返回 false 。 题目思考 可以只需要遍历一遍节点得到结果吗? 解决方案 思路 有了昨天剑指 Offer 55 - I. 二叉树的深度 - leetcode 剑指 offer 系列的铺垫, 这道题相信大家都可以迎刃而解一个比较容易想到的思路是: 先计算出每个节点的深度, 并将其存入节点=>深度字典中; 然后再遍历一遍节点, 针对每个节点, 判断它左右子节点的深度是否满足要求, 所有节点都满足的话才说明平衡. 但是这种方案需要遍历两边节点, 效率不太高, 如何一次性遍历得出结果呢?回顾递归求深度的方案
  • 菜鸡刷leetcode 剑指 Offer 55 - I. 二叉树的深度
    # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def maxDepth(self, root: TreeNode) -> int: if root == None: return 0 return max(1,self.maxDepth(root.left)+1,self.maxDepth(root.right)+1) 用递归就几行就vans。也是很绝。 这个要记住: 1.树的深度 = max(左子树深度+1,右子树深度+1) 2.如果只有一个节点,树的深度 = 1 3.如果没有节点,树的深度时0 3是递归结束的条件 来源:https://blog.csdn.net/weixin_45495647/article/details/115385518
  • 剑指 Offer 总结 - leetcode 剑指offer系列
    剑指 Offer 系列完结撒花!! 🎉🎉 本篇文章是对整个系列的精华总结, 对系列的每篇文章进行了分类, 并用一句话概括每道题的思路, 方便大家理解和记忆, 当然也包含原文完整链接供大家参考 总的来说, 写这个系列耗费了我不少精力, 不过我也很开心能和大家分享, 真心希望能对大家有所帮助, 也希望大家能够多多点赞转发和分享, 让更多人看到, 谢谢~ 接下来我需要休整一段时间来准备新的系列了, 中间也可能会有一些不定期更新. 至于新系列是什么呢? 大家敬请期待 😝 P.S. 公众号即将改名为 算法精选, 更简短和好记, 并且新加了一个暗号 剑指总结. 进入公众号 算法精选, 在聊天框中回复 剑指总结 就能快速定位到这篇文章啦~ 目录 数字/数组 剑指 Offer 03. 数组中重复的数字 - leetcode 剑指 offer 系列剑指 Offer 04. 二维数组中的查找 - leetcode 剑指 offer 系列剑指 Offer 11. 旋转数组的最小数字 - leetcode 剑指 offer 系列剑指 Offer 14- I. 剪绳子 - leetcode 剑指 offer 系列剑指 Offer 14- II. 剪绳子 II - leetcode 剑指 offer 系列剑指 Offer 17. 打印从 1 到最大的 n 位数 - leetcode 剑指 offer 系列剑指
  • LeetCode题解目录
    最新更新于2020.11.27 前往LeetCode主页。 前往GitHub源码。(服务器原因,暂停同步。) 前往码云主页。 已解决 456/1878 - 简单353 中等 90 困难 13 2020.06.30 - 2020.07.09,AC + 100道,累计100道。2020.07.10 - 2020.07.19,AC + 100道,累计200道。2020.07.20 - 2020.08.10,AC + 100道,累计300道。2020.08.11 - 2020.11.04,AC + 100道,累计400道。 参赛记录 场次题解LeetCode 第200场周赛LeetCode 1534. 统计好三元组(第200场周赛第1题)LeetCode 1535. 找出数组游戏的赢家(第200场周赛第2题)LeetCode 1536. 排布二进制网格的最少交换次数(第200场周赛第3题)LeetCode 1537. 最大得分(第200场周赛第4题)LeetCode 第201场周赛LeetCode 1544. 整理字符串(第201场周赛第1题)LeetCode 1545. 找出第 N 个二进制字符串中的第 K 位(第201场周赛第2题)LeetCode 1546. 和为目标值的最大数目不重叠非空子数组数目(第201场周赛第3题)LeetCode 1547. 切棍子的最小成本
  • Leetcode刷题笔记题解(C++):剑指 Offer 55 - II. 平衡二叉树
    二叉平衡树: 它或者是一颗空树,或它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。 如果该树不为空,则需要满足2个条件即为二叉平衡树 (1)左右子树深度差小于等于1 (2)左右子树皆为二叉平衡树 代码如下:(说明一下,代码的时间复杂度很大,但是代码比较容易理解一些,后面再进行优化) /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isBalanced(TreeNode* root) { if(!root) return true; //判断深度是否符合 bool valid_depth=abs(depth(root->left)-depth(root->right))<2; //判断左右子树是否为平衡二叉树 bool valid_son=isBalanced(root->left)&&isBalanced(root->right); return valid_depth; } /
  • leetcode刷题目录
    leetcode大神 https://www.cnblogs.com/grandyang/p/4606334.html https://github.com/gzwl/leetcode https://blog.csdn.net/lanxu_yy/column/info/leetcode-solution 电子书下载 目标:在我职业生涯的前3年,至少把leetcode上的题刷完一半 刷题oj:https://www.luogu.com.cn/problem/list?orderBy=difficulty&order=asc&difficulty=1&page=1 排序 交换类排序 – 冒泡排序 鸡尾酒排序 奇偶排序 梳子排序 侏儒排序 快速排序 臭皮匠排序 Bogo 排序 选择类排序 – 选择排序 堆排序 Smooth 排序 笛卡尔树排序 锦标赛排序 圈排序 插入类排序 – 插入排序 希尔排序 二叉查找树排序 图书馆排序 耐心排序 归并类排序 – 归并排序 梯级归并排序 振荡归并排序 多相归并排序 Strand 排序 分布类排序 – 美国旗帜排序 珠排序 桶排序 计数排序 鸽巢排序 相邻图排序 基数排序 混合类排序 – Tim 排序 内省排序 Spread 排序 UnShuffle 排序 J 排序 Java如何生成长度为n,范围为[l, r]的随机整数数组 什么是稳定排序
  • 《剑指Offer》题解汇总索引表(leetcode)
    《剑指Offer》题解汇总索引表(leetcode) 🎈 文章目录 《剑指Offer》题解汇总索引表(leetcode)[【LeetCode】《剑指Offer》第Ⅰ篇⊰⊰⊰ 3 - 11题](https://blog.csdn.net/weixin_44368437/article/details/114194973)[【LeetCode】《剑指Offer》第Ⅱ篇⊰⊰⊰ 12 - 19题](https://blog.csdn.net/weixin_44368437/article/details/114220348)[【LeetCode】《剑指Offer》第Ⅲ篇⊰⊰⊰ 20 - 31题](https://blog.csdn.net/weixin_44368437/article/details/114229562)[【LeetCode】《剑指Offer》第Ⅳ篇⊰⊰⊰ 32 - 38题](https://blog.csdn.net/weixin_44368437/article/details/114249554)[【LeetCode】《剑指Offer》第Ⅴ篇⊰⊰⊰ 39 - 47题](https://blog.csdn.net/weixin_44368437/article/details/114266808)[【LeetCode】《剑指Offer》第Ⅵ篇⊰⊰⊰ 48 - 55题]
  • [剑指-Offer] 0. 《剑指-Offer》面试题题解汇总
    剑指-Offer 该专栏收录了学习《剑指-Offer》第二版书中的面试题,书中编程题是新大多以 LeetCode 对应系列的线上 OJ 给解答,下面会以章节的形式给出博主总结的本书中各个面试题的链接,方便对应查阅、学习。 第 2 章:面试需要的基础知识 2.2 编程语言 [剑指-Offer] 1. 赋值运算符函数(编程语言、细节处理、代码优化) [剑指-Offer] 2. 实现Singleton模式(单例模式、细节处理、代码优化) 2.3 数据结构 [剑指-Offer] 3. 数组中重复的数字(哈希、抽屉原理、代码优化、多方法) [剑指-Offer] 4. 二维数组中的查找(数学、二分法) [剑指-Offer] 5. 替换空格(反向思维、代码优化、多方法) [剑指-Offer] 6. 从尾到头打印链表(链表逆置、递归、鲁棒性、多方法) [剑指-Offer] 7. 重建二叉树(二叉树、递归建树) [剑指-Offer] 8. 二叉树的下一个结点(多情况分析、画图分析) [剑指-Offer] 9. 用两个栈实现队列(栈、队列、模拟) 2.4 算法和数据操作 [剑指-Offer] 10. I. 斐波那契数列及II. 青蛙跳台阶问题(递归、fib快速计算、fib求和公式、fib通项公式) [剑指-Offer] 11. 旋转数组的最小数字(二分法、分治、递归) [剑指-Offer] 12
  • 剑指 Offer 55 - I. 二叉树的深度 剑指 Offer 55 - II. 平衡二叉树
    剑指 Offer 55 - I. 二叉树的深度 难度:简单 题目描述 解题思路 简简单单普普通通的递归 /* * 剑指 Offer 55 - I. 二叉树的深度 * 2020//8/1 */ public int maxDepth(TreeNode root) { if(root == null) { return 0; } int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left, right)+1; } 剑指 Offer 55 - II. 平衡二叉树 难度:简单 这道题可以直接用上面那道题的代码,分别比较左右子树的高度差是不是大于1。但是这样做效率不高,因为是从顶向下的,而且没有记忆化,每个节点都访问了多次。 /* * 剑指 Offer 55 - II. 平衡二叉树 * 2020/8/1 难度:简单 */ public boolean isBalanced(TreeNode root) { if(root == null) { return true; } int left = maxDepth(root.left); int right = maxDepth(root.right); if(Math.abs(left-right) > 1) { return
  • 剑指offer - 55 - I. 二叉树的深度
    题目描述 输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。 例如: 给定二叉树 [3,9,20,null,null,15,7], 3 / 9 20 / 15 7 返回它的最大深度 3 。 提示: 节点总数 <= 10000 注意:本题与leetcode 104 题相同。 思路1:先序遍历 二叉树的深度 = 左右子树深度的较大值 + 1 代码 class Solution { public int maxDepth(TreeNode root) { if (root == null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) +1; } } 执行用时 : 0 ms, 在所有 Java 提交中击败了100.00%的用户 内存消耗 : 39.6 MB, 在所有 Java 提交中击败了100.00%的用户 思路2:层序遍历 用队列实现。每遍历一层,则计数器 +1 ,直到遍历完成,则可得到树的深度。 class Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; Queue<TreeNode> queue = new
  • LeetCode每日打卡(长久更新) Java, 欢迎打卡互关
    每日做题,欢迎指正 力扣个人主页:https://leetcode-cn.com/u/yunshuibing/ 欢迎打卡互关 这个并不是题解集锦,我会把感觉难一些的题目附上推荐的题解,毕竟一个刷题的,写题解怎么说也没有大佬专门花时间写的详细。与其看写的不清不白的,不如直接去看优质题解,因此这就是个刷题打卡的博客,欢迎来互相督促(虽然没人看~~~)。 题目标签1.两数之和(简单)哈希表2.两数相加(简单)链表3.无重复字符的最长子串(中等)滑动窗口5.最长回文子串(中等)7.整数反转(简单)8.字符串转换整数(atoi)(中等)字符串9.回文数(简单)11.盛最多水的容器(中等)双指针15.三数之和(中等)双指针16.排序加双指针(中等)双指针18.四数之和(中等)双指针19.删除链表的倒数第N个节点(中等)链表20.有效的括号(简单)21.合并两个有序链表(简单)链表26.删除排序数组中的重复项(简单)双指针36.有效的数独(中等)39.组合总和(中等)DFS、剪支40.组合总和II(中等)DFS、剪支42.接雨水(困难)单调栈43.字符串相乘(中等)46.全排列(中等)回溯50.Pow(x,y)快速幂53.最大子序和(简单)动规55.跳跃游戏(中等)56.合并区间(中等)排序58.最后一个单词的长度(64.最小路径和(中等)动规70.爬楼梯(简单)动规71.简化路径(中等)栈
  • LeetCode(剑指offer-tree)-面试题55 - I. 二叉树的深度
    输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。 例如: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。 提示: 节点总数 <= 10000 链接:https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof 树的遍历方式总体分为两类:深度优先搜索(DFS)、广度优先搜索(BFS); 常见的 DFS : 先序遍历、中序遍历、后序遍历;常见的 BFS : 层序遍历(即按层遍历)。 求树的深度需要遍历树的所有节点,本文将介绍基于 后序遍历(DFS) 和 层序遍历(BFS) 的两种解法。 方法一:后序遍历(DFS) 树的后序遍历 / 深度优先搜索往往利用 递归 或 栈 实现,本文使用递归实现。关键点: 此树的深度和其左(右)子树的深度之间的关系。显然,此树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +1。 算法解析: 终止条件: 当 root​ 为空,说明已越过叶节点,因此返回 深度 0 。递推工作: 本质上是对树做后序遍历。 计算节点 root​ 的 左子树的深度 ,即调用 maxDepth(root.left);计算节点 root​ 的 右子树的深度
  • [剑指-Offer] 55 - I. 二叉树的深度及II. 平衡二叉树(二叉树、后序遍历、代码优化、巧妙解法)
    文章目录 1. 题目来源2. 题目说明3. 题目解析 --- I. 二叉树的深度方法一:递归+常规解法 4. 题目解析 --- II. 平衡二叉树方法一:递归+常规解法方法二:递归优化+巧妙解法 1. 题目来源 链接:I. 二叉树的深度 链接:II. 平衡二叉树 来源:LeetCode——《剑指-Offer》专项 2. 题目说明 3. 题目解析 — I. 二叉树的深度 方法一:递归+常规解法 从根节点开始遍历: 若仅有根节点,则深度为 1若根节点只有左子树没有右子树,则深度为左子树深度 +1若根节点只有右子树没有左子树,则深度为左子树深度 +1若左右子树均存在,则该树的深度为其左子树、右子树的深度的较大值再 +1 这样就可以采用递归的思路进行实现了。 参见代码如下: // 执行用时 :16 ms, 在所有 C++ 提交中击败了46.43%的用户 // 内存消耗 :21.4 MB, 在所有 C++ 提交中击败了100.00%的用户 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class
  • 经典算法题思路整理
    Principle 自己能在面试中A4纸写出来的代码才是好代码,不要一味追求复杂度低的代码,如果写都写不出来更不用谈复杂度。第一遍先大概粗过一遍题目思路,第二遍再刷代码。标注出不熟悉的题目,隔天复习,加强记忆。 数组 数学 字符串 链表 二叉树 回溯、搜索 动态规划 排序等 其他 数组 DescriptionSolution287. 寻找重复数hashmap、排序、二分变形283. 移动零双指针、冒泡剑指 Offer 50. 第一个只出现一次的字符哈希1. 两数之和哈希167. 两数之和 II - 输入有序数组、剑指 Offer 57. 和为s的两个数字哈希或双指针!!!581. 最短无序连续子数组双指针88. 合并两个有序数组双指针977. 有序数组的平方!!! 75. 颜色分类荷兰旗问题!!!334. 递增的三元子序列三指针---------------------------------------------剑指 Offer 57 - II. 和为s的连续正数序列滑动窗口集合交集哈希、排序剑指 Offer 66. 构建乘积数组、LeetCode 238. 除自身以外数组的乘积乘积=当前数左边的乘积*当前数右边的乘积Leetcode 35. 搜索插入位置二分4. 寻找两个正序数组的中位数二分34. 在排序数组中查找元素的第一个和最后一个位置二分153
  • [剑指 offer]--树-- 面试题55 - I. 二叉树的深度
    1 题目描述 输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。 2 解题思路 树的遍历方式总体分为两类: 深度优先搜索(DFS)、广度优先搜索(BFS); 常见的 DFS : 先序遍历、中序遍历、后序遍历; 常见的 BFS : 层序遍历(即按层遍历)。 方法一:先序遍历(DFS) 树的先序遍历 / 深度优先搜索往往利用 递归 或 栈 实现,本文使用递归实现。 关键点: 此树的深度和其左(右)子树的深度之间的关系。显然,此树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +1 。 算法解析: 终止条件: 当 root​ 为空,说明已越过叶节点,因此返回 深度 0 。递推工作: 本质上是对树做先序遍历。 计算节点 root​ 的 左子树的深度 ,即调用 maxDepth(root.left) ; 计算节点 root​ 的 右子树的深度 ,即调用 maxDepth(root.right) ;返回值: 返回 此树的深度 ,即 max(maxDepth(root.left), maxDepth(root.right)) + 1 。 复杂度分析: 时间复杂度 O(N) : N 为树的节点数量,计算树的深度需要遍历所有节点。 空间复杂度 O(N) : 最差情况下(当树退化为链表时),递归深度可达到 N 。