xqxls

分类

二叉树技巧总结(2) 未归档(3) 题解(292)

/ 注册

TA的专栏 297篇文章 4人订阅

297篇文章 4409人学习

全部文章（共248篇）

题解 | #重建二叉树# 来自专栏

方法一（递归+哈希表） 1.题意整理给定一颗二叉树的前序遍历序列和中序遍历序列。重建该二叉树，并返回头节点。 2.思路整理因为前序遍历是按根、左、右的顺序访问节点，中序遍历是按左、根、右的顺序访问节点。一个朴素的思路是，先找到前序序列的第一个元素，将其作为头节点，然后通过遍历中序序列，找到...

Java

2022-01-28

0 363

题解 | #二叉树中和为某一值的路径(二)# 来自专栏

方法一（深度优先搜索） 1.题意整理给定一颗二叉树以及一个整数expectNumber，二叉树中每个节点对应一个节点值。找出二叉树中所有的从根节点到叶子节点的节点值之和等于expectNumber的路径。 2.思路整理可以利用深度优先搜索，遍历所有可能的路径，然后看某个路径的和是否等于ex...

Java

2022-01-28

0 427

题解 | #判断是不是平衡二叉树# 来自专栏

方法一（递归+剪枝） 1.题意整理给定一颗二叉树。判断该二叉树是否是平衡二叉树。如果一颗二叉树是空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树，则这颗二叉树是平衡二叉树。 2.思路整理一个朴素的想法是，先利用递归计算树中每颗子树的高度，然后再根据子树高度差...

Java

2022-01-28

0 383

题解 | #求二叉树的层序遍历# 来自专栏

方法一（BFS） 1.题意整理给定一颗二叉树。求二叉树的层序遍历。 2.思路整理广度优先搜索的过程一般是将源节点入队，然后将当前节点出队，同时找到所有可到达的节点再次入队。循环这个过程，直到遍历完所有的节点。二叉树的层序遍历是一种特殊的广度优先搜索，当前队列中节点的个数即为当前层中节点数目...

Java

2022-01-28

0 598

题解 | #二叉树的最大深度# 来自专栏

方法一（递归） 1.题意整理给定一颗二叉树。求二叉树的最大深度。深度是指树的根节点到任一叶子节点路径上节点的数量。 2.思路整理按照二叉树递归的套路，需要考虑当前节点的情况、当前节点左子树的情况、当前节点右子树的情况。只要知道当前节点左右子树的深度，那么当前节点为根的子树的深度即为两者中较...

Java

2022-01-28

0 330

题解 | #二叉树中和为某一值的路径(一)# 来自专栏

方法一（深度优先搜索） 1.题意整理给定一颗二叉树以及一个值sum，二叉树中每个节点对应一个节点值。判断二叉树中是否有从根节点到叶子节点的节点值之和等于sum的路径。 2.思路整理可以利用深度优先搜索，遍历所有可能的路径，然后看某个路径的和是否等于sum，如果存在这样的路径，则直接返回tr...

Java

2022-01-28

0 309

题解 | #二叉树中的最大路径和# 来自专栏

方法一（递归） 1.题意整理给定一颗二叉树，二叉树中每个节点对应一个节点值。求二叉树中的最大路径和，其中路径指的是从任意节点出发到另一个节点之间所经过的路径。 2.思路整理对于二叉树的大部分题目，都可以试图分三种情况进行考虑，分别是当前节点的情况、当前节点左子树的情况、当前节点右子树的情况...

Java

2022-01-28

0 339

题解 | #二叉树根节点到叶子节点的所有路径和# 来自专栏

方法一（深度优先搜索） 1.题意整理给定一颗二叉树，二叉树中每个节点对应一个节点值（在0-9范围内）。求二叉树中所有路径的和，每一条路径指的是从根节点到某一个叶子节点这一串节点值从高位到低位组成的数。 2.思路整理题目需要求所有路径和，所以只要找出每一条路径，然后记录对应路径的变化，最后将...

Java

2022-01-27

0 361

题解 | #给表达式添加运算符# 来自专栏

题意整理给定一个仅包含数字的字符串num和一个目标值target。在num的数字之间添加"+","-"或"*",返回所有能够得到目标值的表达式。方法一（位运算） 1.解题思路可以分两步解决，第一步将运算符添加到字符串num，组成一个表达式，找到所有可能的表达式，第二步校验生成的表达式，计...

Java

2022-01-20

0 667

题解 | #检测循环依赖# 来自专栏

题意整理给定n门课程，这n门课程中存在一定的依赖关系，例如想要完成B课程，必须先完成A课程。依赖关系存储在一个数组里。找出可以完成所有课程的一个顺序列表，如果不能完成所有课程，返回一个空数组。方法一（深度优先搜索） 1.解题思路新建一个邻接表，记录所有课程对应的后置课程。新建一个vis...

Java

2022-01-19

2 1225