a_fighter_named_rudy

分类

/ 注册

全部文章（共15篇）

题解 | #插入二叉搜索树#

简单题：val和当前结点比较，如果大于当前结点则往右走，小于则往左走，走到空的地方即是val的位置。 class Solution { public: /** ...

C++

2022-11-02

0 336

题解 | #二叉树的下一个结点#

解答：首先如果此题没有空间复杂度要求那就是简单题，思考不用数组的方法，首先输入的不是根结点，而是目标结点，所以第一步得通过next，找到该树的根结点，找根结点之前得把目标结点的val保存到target；然后通过中序遍历开始访问，逻辑写在中间即中序遍历，我们通过一个flag标志来解决先后关系，首先如果...

C++

2022-11-02

0 298

题解 | #树的子结构#

解答：首先因为结点值可能重复，所以得考虑双递归，一个递归遍历所有结点，一个递归判断是否是子结构，因此时间复杂度为O(n^2)，空间复杂度为O(1)。注意当成功找到一个以后得保存答案或者直接返回，要不然可能后续还有点的值相等但不是子结构，会将答案改为false。 class So...

C++

2022-11-02

0 300

题解 | #将二叉搜索树改为累加树#

解答：根据此题的题意，访问顺序为右根左，得先一直访问到最右下角的点，即最大点，记录这个最大值max，然后因为没有比最大还大的所以不更新，然后往上更新根结点，根结点+=max，然后更新max，把这个逻辑写在右根左的中间即中序遍历。时间复杂度为O(n),空间复杂度为O(1)。 class&...

C++

2022-10-28

0 352

题解 | #二叉树的最小深度#

解答：与求二叉树的最大深度有异曲同工之妙，均用后序遍历来做，但是最大深度是返回max(l,r)+1，而此题思考题意，要分3种情况，①当左右子树均为0则返回1，②当左右子树中有一个为0，则返回其中不为0的那个并且+1，③当左右子树均不为0则返回min(l,r)+1。因为遍历了所有结点所以时间复杂度O(...

C++

2022-10-28

0 397

题解 | #二叉树的最大宽度#

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请...

C++

2022-10-27

0 360

题解 | #二叉树中和为某一值的路径(三)#

解答：看到所有字眼，立即思考双递归，其中一个递归遍历所有节点，一个递归求解逻辑。根据题意路径只能是父亲往下，则往下找就ok，但需要注意一个问题就是一般问题写习惯了找到以后习惯性return，而这题不能return，因为可能两条路径某些节点完全重合，即该条路径终点如果不是叶子节点，则继续往下可能还有满...

C++

2022-10-27

0 288

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

解答：简单dfs问题，遍历所有路径将满足条件的路径存入res即可。但有一点需要注意就是必须是叶子节点满足才行，如果非叶子节点和等于target也不能输出。时间复杂度因为遍历了所有节点所以为O(n),空间复杂度也为O(n)。 class Solution { ...

C++

2022-10-26

0 262

题解 | #重建二叉树#

通过前序遍历和中序遍历即可确定一颗树，树的题目直接思考递归，因此对此题，首先可发现前序遍历的第一个元素为根节点，则在中序遍历中找到该根节点即可将该树的左右子树找出。因此可递归，第一次输入两个完整数组，将pre数组的p[0]变为树节点，则左接(cutpre,cutvin)，右接(cutpre,cutv...

C++

2022-10-26

0 275

题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树#

看到二叉搜索树就思考中序遍历，如果是二叉搜索树则中序遍历结果数组应该为升序数组。对完全二叉树使用层序遍历，对于空节点则用一个-1来占位。最后判断层序遍历结果-1后面是否存在有效数字，如果存在则不是完全二叉树。二叉搜索树遍历和判断是否升序时间复杂度为O(n)，层序遍历和判断是否有序时间复杂度为O(n)...

C++

2022-10-26

0 0