retyrn

分类

题解(3)

/ 注册

全部文章（共206篇）

题解 | #牛群的最短路径# 自顶向下遍历二叉树

知识点二叉树思路自顶向下遍历二叉树，维护长度，到叶子节点时更新答案，注意空节点长度为0。时间复杂度每个节点只会遍历一次，时间复杂度为AC code （C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * stru...

2023-07-21

0 288

题解 | #牛的奶量统计# 自顶向下DFS

知识点DFS思路自顶向下去维护从根节点到子节点的路径和，当子节点为叶子节点时更新答案。注意当res已经为true或者路径和已经大于target时的及时剪枝。时间复杂度每个节点至多访问一次，时间复杂度为AC code （C++） /** * struct TreeNode { * int val;...

2023-07-21

0 214

题解 | #牛的奶量统计II# DFS

知识点DFS multiset思路将任意节点到它的子节点的路径，拆分为任意子节点到根节点的路径 - 任意节点到根节点的路径。我们在dfs的过程中，用multiset维护根节点这个节点的祖先节点的和，去查找是否有满足要求的根节点到其祖先节点的合法路径。注意sum超过target及时剪枝。时间复杂度遍...

2023-07-21

0 257

题解 | #牛群的秘密通信# 栈

知识点栈思路判断括号序列，可以建一个栈，遇到左括号将其压栈，遇到右括号则取出栈顶元素看是否匹配，如果栈为空或者栈顶元素不匹配则返回false，都匹配好后不可以剩下左括号不匹配，验证栈是否为空。时间复杂度只有遍历一遍字符串，时间复杂度为AC code（C++） class Solution { pub...

2023-07-21

0 222

题解 | #牛的表达式计算器# 后缀表达式求值

知识点后缀表达式栈思路后缀表达式求值，可以一个栈来记录数字，每当遇到预算符号，取出栈顶的两个数字进行运算，把结果重新入栈。最后的栈顶即为全部的计算结果。时间复杂度只遍历了一遍数组，每次出入栈的次数是常数次，时间复杂度为AC code（C++） class Solution { public: ...

2023-07-21

0 332

题解 | #牛群的二叉树排序# 完全二叉树

知识点完全二叉树层序遍历思路题目要求统计0和1的数量，分别在根节点的左右子树建立完全二叉树，然后返回根节点。我们遍历数组统计0和1的个数，之后利用层序遍历（BFS）的方法建立完全二叉树，并返回根节点作为答案的左右子树。具体见代码。时间复杂度由于只会建立n个节点并每个节点遍历一次，时间复杂度为AC...

2023-07-20

0 253

题解 | #牛群排列的最大深度# 递归

知识点二叉树递归思路二叉树的最大深度，等于左右子树的最大深度中的较大值+1；因此可以先求子树的最大深度，而这是一个和原问题一样的子问题，可以用递归解决。递归终点是空节点，深度为0。时间复杂度只遍历一遍二叉树AC code （C++） /** * struct TreeNode { * int...

2023-07-20

0 257

题解 | #二叉树之寻找第k大# 二叉搜索树

知识点二叉搜索树思路求二叉搜索树的第k大值。二叉搜索树的中序遍历是递增序列，我们可以稍作修改，先遍历右子树，再根节点，再左子树，即可得到递减序列。当遍历的节点数到达k时，更新答案并及时剪枝。时间复杂度由于及时剪枝，时间复杂度为AC code (C++) /** * struct TreeNode ...

2023-07-20

0 267

题解 | #牛群中的编号是否有效# 二叉搜索树

知识点二叉搜索树思路验证二叉搜索树，需要验证左右子树是不是都是BST。然后再判断当前值是不是比左子树的所有值都大，比右子树所有值都小，实现上只需要验证左子树，因为如果右子树不满足条件，会在遍历右子树的时候不满足条件。时间复杂度遍历一遍二叉树，时间复杂度是线性的 AC code （C++） /** ...

2023-07-20

0 196

题解 | #第k轻的牛牛# 二叉搜索树

知识点二叉搜索树思路要求出二叉树中第k小的值，二叉搜索树的中序遍历得到的是递增序列，因此只要跑中序遍历，搜索个数达到k后更新答案并及时剪枝。时间复杂度由于及时剪枝，总体时间复杂度是AC code （C++） /** * struct TreeNode { * int val; * struct...

2023-07-20

0 248