wkkw

题解

/ 注册

全部文章 / 题解（共70篇）

题解 | #栈的压入、弹出序列#

这个题还是比较好理解，关键点在使用辅助栈。题目最重要的信息是栈里的数据是唯一，这样在当前是否需要出栈的时候，可以用相等作为判断条件。没有这个条件的化，栈里有很多相同的数，题目会很麻烦。需要回溯。 class Solution { public: &nb...

C++

2022-01-15

11 638

题解 | #包含min函数的栈#

这个题官方解比较巧妙 class Solution { public: stack<int> data,minData; void push(int...

C++

2022-01-15

0 379

题解 | #二叉搜索树的最近公共祖先#

这个题分类处理就好，我选择的是先序遍历，这样比较好处理。情况1：发现节点值在寻找的两个节点值中间，并且不等于其中任何一个，不用找了，已经找到了。情况2：发现节点值等于寻找的两个值中较小的那个，那么只要大的那个在当前节点的左子树上就找到了，否则继续。情况3：发现节点值等于寻找的...

C++

2022-01-15

0 274

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

这个题虽然是中等，代码也不多，解法也有很多，但是特别高效的我也没找到。看到了很多双递归解法，确实巧妙。但是我觉得单递归+一次路径遍历效率上应该更高一点。解法1：把dfs所有的根节点到叶子节点路径列找到，然后单个路径使用滑动窗口，窗口路径和为sum则计数+1。解法2： d...

C++

2022-01-13

0 335

题解 | #序列化二叉树#

这个题虽然官方说很简单，两颗星，实现的代码看起来也简单。难点在下面个地方： 1.中序跟后序遍历实现起来非常麻烦，我现在还不会。 2.先序遍历解码是时候需要注意是指针引用。因为只有指针引用才能保证每次方法调用的是同一个指针。 3.需要注意序列化的时候加入分隔符，非常关键。在反...

C++

2022-01-11

2 429

题解 | #对称的二叉树#

这个一个dfs就可以解决了。需要注意的是特殊情况判断，左右子树都为空直接返回true.左右一个空，一个非空，肯定就直接false.两个都非空，但是值不相等，直接false。其他情况继续判断下去。注意的是这个是镜像，意味着是左子树的左孩子跟右子树的有孩子判断，左子树的右孩子跟右...

C++

2022-01-08

0 321

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

这个题虽然不是很难，提交了4次才算通过。有点汗颜，如果是面试可能就挂了，思路还是比较清楚的。我们分情况讨论。 1.给出的节点存在右子节点的情况。比较好处理，也不需要回溯。dfs就可以搞定。就一直找到右边节点的中序遍历的第一个节点就可以了。 2.不满足1，但是它存在父节点。 ...

C++

2022-01-08

0 329

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

跟前一个题差不多，唯一的区别是深度优先遍历的参数稍作调整。路径回退的时候需要pop当前路径，这个要注意一下。记录路径当然要有当前路径，最后的结果也需要记录。 /* struct TreeNode { int val; struct Tr...

C++

2022-01-07

0 328

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

这个题虽然是个简单题，但是也不是不需要动脑筋。简单的dfs还是要会的。稍微注意的是那个返回值，使用值引用会更好。然后找到路径就提前退出。 /** * struct TreeNode { * int val; &n...

C++

2022-01-07

0 357

题解 | #二叉搜索树的第k个节点#

此题考的是深度优先搜索，遍历一遍，保存起来。取第k个就好。当然需要提前退出，数组长度大于等于K，就不需要遍历后面的节点了。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right...

C++

2022-01-07

0 386