展开

关键词

第35期:从 DFS 学习!(适合小白)

在计算机科学中,是每个结点最多有两个子结构。通常子被称作“左子”(left subtree)和“右子”(right subtree)。常被于实现查找堆。 01、题目分析第104题:最大深度给定一个,找出其最大深度。深度为根节点到最远叶子节点最长路径上节点数说明: 叶子节点是指没有子节点节点。 示例:给定 , 3 9 20 15 7 02、解我们知道,每个节点深度与它左右子深度有关,且等于其左右子最大深度值加上 1 。 即: maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1以 为例:我们要对根节点最大深度解,就要对其左右子深度进行解 如上图,它访问顺序为: A-B-D-E-C-F-GA-B-D-E-C-F-G到这里,我们思考一个问题?虽然我们方式根据DFS思想顺利完成了题目。但是这种方式缺点却显而易见。

15120

漫画:系列 第一讲(最大深度与DFS)

在计算机科学中,是每个结点最多有两个子结构。通常子被称作“左子”(left subtree)和“右子”(right subtree)。常被于实现查找堆。 01第104题:最大深度第104题:给定一个,找出其最大深度。深度为根节点到最远叶子节点最长路径上节点数。说明: 叶子节点是指没有子节点节点。 示例:给定 , 3 9 20 15 7本系列内容均为必须掌握!02解我们知道,每个节点深度与它左右子深度有关,且等于其左右子最大深度值加上 1。 即:maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1以 为例:我们要对根节点最大深度解,就要对其左右子深度进行解我们看出 如上图,它访问顺序为:A-B-D-E-C-F-G到这里,我们思考一个问题?虽然我们方式根据DFS思想顺利完成了题目。但是这种方式缺点却显而易见。

24810
  • 广告
    关闭

    90+款云产品免费体验

    提供包括云服务器,云数据库在内的90+款云计算产品。打造一站式的云产品试用服务,助力开发者和企业零门槛上云。

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    漫画:系列 第一讲(最大深度与DFS) 修订版

    在计算机科学中,是每个结点最多有两个子结构。通常子被称作“左子”(left subtree)和“右子”(right subtree)。常被于实现查找堆。 01第104题:最大深度第104题:给定一个,找出其最大深度。深度为根节点到最远叶子节点最长路径上节点数。说明: 叶子节点是指没有子节点节点。 示例:给定 , 3 9 20 15 7本系列内容均为必须掌握!02解我们知道,每个节点深度与它左右子深度有关,且等于其左右子最大深度值加上 1。 即:maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1以 为例:我们要对根节点最大深度解,就要对其左右子深度进行解我们看出 如上图,它访问顺序为:A-B-D-E-C-F-G到这里,我们思考一个问题?虽然我们方式根据DFS思想顺利完成了题目。但是这种方式缺点却显而易见。

    19530

    入门和刷题看这篇就够了!

    maxDepth(sub-7))+1)+1=max(1,max(1,1)+1)+1=max(1,2)+1=3根据分析,我们通过进行解: 1Go 2func maxDepth(root *TreeNode 这也是为什么我们一般不在后台代码中使原因。如果不理解,下面我们详细说明:事实上,函数调参数是通过栈空间来传,在调过程中会占线程栈资源。 而,只有走到最后结束点后函数才能依次退出,而未到达最后结束点之前,占栈空间一直没有释放,如果次数过多,就可能导致占栈资源超过线程最大值,从而导致栈溢出,导致程序异常退出。 那如何通过非DFS方式,来对本题解呢?相信已经很简单了,这个下去自己试试就ok了了。 比如下面这颗:这个就不是:上面做了这么多题了,你应该能想到我要说啥 --- 题目基本上都可以解。

    24430

    :看看这些最大深度

    最大深度会了,那么顺手把N也做了吧❞104.最大深度给定一个,找出其最大深度。深度为根节点到最远叶子节点最长路径上节点数。 说明: 叶子节点是指没有子节点节点。示例:给定 ,?返回它最大深度 3 。思路法本题其实也要后序遍历(左右中),依然是因为要通过函数返回值做计算高度。 代码如下:if (node == NULL) return 0; 确定单层逻辑:先左子深度,再右子深度,最后取左右深度最大数值 再+1 (加1是因为算上当前中间节点)就是目前节点为根节点深度 迭代法使迭代法话,使层序遍历是最为合适,因为最大深度就是层数,和层序遍历方式极其吻合。在中,一层一层来遍历,记录一下遍历层数就是深度,如图所示:? 思路依然可以提供法和迭代法,来解决这个问题,思路是和思路一样,直接给出代码如下:法C++代码:class Solution {public: int maxDepth(Node* root

    21320

    最大深度

    深度为根节点到最远叶子节点最长路径上节点数。说明:叶子节点是指没有子节点节点。示例:给定 , 3 9 20 15 7 返回它最大深度 3 。 解题思路题目要最大深度,我们知道,每个节点深度与它左右子深度有关,且等于其左右子最大深度值加上 1,可以写作:maxDepth(root) = max(maxDepth(root.left 由此可见,「节点最大深度」是该题子问题,该题最直观解答方式是解。设计在算法中,函数设计非常重要,首先我们要先明确该函数,然后再确定何时结束与何时调该函数。 空间复杂度考虑到使栈(call stack)情况。最坏情况:完全不平衡。例如每个节点都只有右节点,此时将 n 次,需要保持调存储为 O(n)最好情况:完全平衡。 即高度为 log(n),此时空间复杂度为 O(log(n))总结一下与相关题目常来解,对于而言,我们需要明确:函数函数结束条件函数自身调时机除此之外,在计算空间复杂度时

    22320

    最大深度

    深度为根节点到最远叶子节点最长路径上节点数。说明:叶子节点是指没有子节点节点。示例:给定 , 3 9 20 15 7 返回它最大深度 3 。 解题思路题目要最大深度,我们知道,每个节点深度与它左右子深度有关,且等于其左右子最大深度值加上 1,可以写作:maxDepth(root) = max(maxDepth(root.left 由此可见,「节点最大深度」是该题子问题,该题最直观解答方式是解。设计在算法中,函数设计非常重要,首先我们要先明确该函数,然后再确定何时结束与何时调该函数。 空间复杂度考虑到使栈(call stack)情况。最坏情况:完全不平衡。例如每个节点都只有右节点,此时将 n 次,需要保持调存储为 O(n)最好情况:完全平衡。 即高度为 log(n),此时空间复杂度为 O(log(n))总结一下与相关题目常来解,对于而言,我们需要明确:函数函数结束条件函数自身调时机除此之外,在计算空间复杂度时

    17510

    LeetCode算法题(一)

    删除链表中节点请编写一个函数,使其可以删除某个链表中给定(非末)节点,你将只被给定要被删除节点。 、104. 最大深度给定一个,找出其最大深度。深度为根节点到最远叶子节点最长路径上节点数。说明: 叶子节点是指没有子节点节点。 = maxDepth(root.left) + 1; if(maxRight > maxLeft){ return maxRight; }else{ return maxLeft; } } }}自评:关于和相关使解题比较容易 ,先设置退出条件,就是两边子为空情况下,体就是一直往下遍历,到最后为空节点,返回最大深度,然后两者相互比较,得出最大深度。 将有序数组转换为搜索将一个按照升序排列有序数组,转换为一棵高度平衡搜索。本题中,一个高度平衡是指一个每个节点 左右两个子高度差绝对值不超过 1。

    17130

    【小Y学算法】⚡️每日LeetCode打卡⚡️——28.最大深度

    C#方法:深度优先搜索思路解析该题是要最大深度,我们可以先出左子和右子深度 l 和 r那就可以计算出最大深度了:max( l,r )+1而左子和右子最大深度又可以以同样方式进行计算 因此我们可以「深度优先搜索」方法来计算最大深度。具体而言,在计算当前最大深度时,可以先计算出其左子和右子最大深度,然后在 O(1) 时间内计算出当前最大深度。 Java 方法一:深度优先搜索思路解析 该题是要最大深度,我们可以先出左子和右子深度 l 和 r那就可以计算出最大深度了:max( l,r )+1而左子和右子最大深度又可以以同样方式进行计算 因此我们可以「深度优先搜索」方法来计算最大深度。具体而言,在计算当前最大深度时,可以先计算出其左子和右子最大深度,然后在 O(1) 时间内计算出当前最大深度。 每个节点在中只被遍历一次。 空间复杂度:O( height ) 其中height 表示高度。函数需要栈空间,而栈空间取决于深度,因此空间复杂度等价于高度。????

    8640

    手把手刷系列完结篇

    traverse(head.next); 后序位置} 单链表和数组遍历可以是迭代,也可以是这种结构无非就是链表,不过没办法简单改写成迭代形式,所以一般说遍历框架都是指形式 这也就是之前 6 篇手把手刷文章核心思想:你只需要思考每一个节点应该做什么,其他你管,抛给遍历框架,会对所有节点做相同操作。 综上,遇到一道题目时思考过程是:是否可以通过遍历一遍得到答案?如果不能话,是否可以定义一个函数,通过子问题(子答案推导出原问题答案? 遍历每个节点时候还会调函数maxDepth,而maxDepth是要遍历所有子,所以最坏时间复杂度是 O(N^2)。 值得一提是,有些很明显需要层序遍历技巧题目,也可以遍历方式去解决,而且技巧性会更强,非常考察你对前中后序把控。

    4920

    LeetCode,Go实现最大深度

    力扣题目:给定一个,找出其最大深度。深度为根节点到最远叶子节点最长路径上节点数。说明: 叶子节点是指没有子节点节点。? ) :首先,我们要知道一棵最大深度在逻辑上怎么? 以左子为例,把它看成新一棵,那么它最大深度就是:根节点高度(根本身为 1 )+ 左右子最大深度中较大者。这样来思考,就发现所在点了。 每个节点在中只被遍历一次。空间复杂度:O(height),其中 height 表示高度。函数需要栈空间,而栈空间取决于深度,因此空间复杂度等价于高度。 我们先将根节点放入队列,然后开始向下遍历,每次拓展下一层时候,需要将队列里所有节点都拿出来进行拓展,使队列里存放是当前层所有节点,我们一个变量 ans 来表示拓展次数,该最大深度即为

    10560

    有多少人真正会

    前言 对数据结构与算法有所了解童鞋,一定对(recursion)并不陌生,事实上在计算机领域中发挥重要,是很多算法和数据结构基础,无论是排序算法(并排序、快速排序),还是对于一些比如数据结构 本文主要通过介绍??是指在函数定义中使函数自身方法。比较典型例子就是斐波拉契数列 f(n) = f(n - 1) + f(n - 2),n ≥ 2。?? 是天然结构。其定义是:如果一个节点,它有左右两个孩子,且左右孩子都是一颗,则就存在一棵以该节点为根。从定义中可看出定义,但在定义里来定义。 因此定义本身就是定义。如下图示。???04. 最大深度 ?给定一个,找出其最大深度。深度为根节点到最远叶子节点最长路径上节点数。 解题思路由于具有天然性,所以可以通过去做, 可以分别计算当前节点左右子最大深度,然后取两者最大值再加 1(当前节点深度),就是这颗最大深度。

    13820

    最大深度

    题目给定一个,找出其最大深度。深度为根节点到最远叶子节点最长路径上节点数。说明: 叶子节点是指没有子节点节点。 示例:给定 , 3 9 20 15 7返回它最大深度 3 。题解最大深度,和深度相关,我们很容易想到层序遍历。每遍历一层,就深度加1, 怎么记录是第几层我们之前文章中讲过了。 = null) { queue.add(current.right); } size--; } depth++; } return depth; }}这道题解代码比较简单.结束条件: 当节点为叶子节点时候 .子问题: 当前最大深度 = 左右子最大深度较大者 + 1代码实现就很简单了。 (maxDepth(root.left), maxDepth(root.right)) + 1; }}

    17120

    每天一道leetcode-104.最大深度

    前言 今天题目每天题目见github(看最新日期):https:github.comgzc426昨天题解题目 给定一个,找出其最大深度。 深度为根节点到最远叶子节点最长路径上节点数。说明: 叶子节点是指没有子节点节点。示例:给定 ,3 9 20 15 7返回它最大深度 3 。 每天一道leetcode-104.最大深度? (root.left);左子深度 int right = maxDepth(root.right);右子深度 return left>right? left+1:right+1;根节点深度是左子和右子深度较高那一个 }}代码截图(避免乱码)?

    15010

    最大深度

    题意给定一个,找出其最大深度。深度为根节点到最远叶子节点距离。 样例给出一棵如下: 1 2 3 4 5这个最大深度为 3.思路分别遍历每个节点 ,返回相对于当前节点最大深度(记得加上根节点)。 循环法非写法可以一个队列来存储,先将根节点存入,并记录当前节点兄弟节点个数(指来自同一个父节点),当兄弟节点都出队列完毕,就对子节点进行与根节点同样操作。 root) { if (root == null) return 0; Queue queue = new LinkedList(); queue.add(root); int depth = 0; 表示深度 if (count == amount) { amount = queue.size(); count = 0; depth++; } } return depth; }} 原题地址LintCode:最大深度

    48420

    leetcode深度

    序本文主要记录一下leetcode深度题目输入一棵根节点,深度。从根节点到叶节点依次经过节点(含根、叶节点)形成一条路径,最长路径长度为深度。 例如: 给定 , 3 9 20 15 7 返回它最大深度 3 。 提示: 节点总数 rightDepth ? leftDepth + 1 : rightDepth + 1; }}小结这里采方式,计算maxDepth(root.left)及maxDepth(root.right),最后取它们最大值+ doc深度

    13520

    leetcode深度

    序本文主要记录一下leetcode深度 deletion-in-binary-tree.png 题目输入一棵根节点,深度。 从根节点到叶节点依次经过节点(含根、叶节点)形成一条路径,最长路径长度为深度。例如:给定 , 3 9 20 15 7返回它最大深度 3 。 leftDepth + 1 : rightDepth + 1; }}小结这里采方式,计算maxDepth(root.left)及maxDepth(root.right),最后取它们最大值+ doc深度

    15400

    LeetCode19|深度

    1,问题简述输入一棵根节点,深度。从根节点到叶节点依次经过节点(含根、叶节点)形成一条路径,最长路径长度为深度。 2,示例给定 , 3 9 20 15 7返回它最大深度 3 3,题解思路使左右子最大高度 4,题解程序public class MaxDepthTest { public TreeNode(15); TreeNode t5 = new TreeNode(7); t1.left = t2; t1.right = t3; t3.left = t4; t4.right = t5; int maxDepth = maxDepth(t1); System.out.println(maxDepth = + maxDepth); } public static int maxDepth(TreeNode root ) { if (root == null) { return 0; } return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; }

    13430

    LeetCode 104: 最大深度 Maximum Depth of Binary Tree

    题目: 给定一个,找出其最大深度。Given a binary tree, find its maximum depth.深度为根节点到最远叶子节点最长路径上节点数。 Note: A leaf is a node with no children.示例:给定 , 3 9 20 15 7 返回它最大深度 3 。 解题思路: 总体而言, 有两种思路:BFS 广度优先遍历时一个变量记录深度DFS 深度优先遍历时保留每次遍历到叶子结点时最大深度对于这道题, DFS 深度优先遍历时若使方法, 又可分为两种思路 : 自顶向下, 自底向上具体可以看这篇文章:遍历 Traverse a Tree类似题目有:LeetCode 559: N 最大深度 Maximum Depth of N-ary Tree 自顶向下解法 int leftDepth = maxDepth(root.left); 右子结点 int rightDepth = maxDepth(root.right); 返回当前结点最大深度 return

    20620

    初级算法-

    摘要大部分问题都可以通过解决,即一个某个值可以转化为左子右子最大深度最大深度就是max(左子最大深度,右子最大深度) + 1(根节点)public int right + 1: left+1; }验证搜索搜索是自左向右有序,可以通过中序遍历,然后判断中序遍历结果是否有序public boolean isValidBST(TreeNode isNodeSymmetric(right.right, left.left) && isNodeSymmetric(right.left, left.right); return result; }层次遍历层次遍历需要利额外数据结构队列 level.isEmpty()) { result.add(level); } } return result;将有序数组转换为搜索搜索本身就是有序,所以将有序数组转换为搜索,就是按照左根右顺序构建 ,根节点就是中间值,使来解决public TreeNode sortedArrayToBST(int nums , int start, int end) { if (start > end)

    14420

    扫码关注云+社区

    领取腾讯云代金券