华科不平凡 - 个人主页动态 - 牛客网

发布(141) 评论刷题收藏

2020-08-22 14:28

华中科技大学 C++

判断二叉树是否对成

两种方法： 递归法——左子树与右子树比较、右子树与左子树比较（3ms + 504KB） 迭代法——借助两个栈实现(3ms + 376KB) 递归 // // Created by jt on 2020/8/22. // using namespace std; class Solution { public: /** * * @param root TreeNode类 * @return bool布尔型 */ bool isSymmetric(TreeNode *root) { // write code here...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-08-22 13:26

华中科技大学 C++

二叉树的层序遍历

用队列实现，每次记录下当前队列的大小即可： // // Created by jt on 2020/8/22. // #include <vector> #include <queue> using namespace std; class Solution { public: /** * * @param root TreeNode类 * @return int整型vector<vector<>> */ vector<vector<int> > levelOrde...

爆辣黄焖鸡：太强了

刷遍天下无敌手

0 点赞评论收藏

分享

2020-08-22 12:32

华中科技大学 C++

二叉树的之字层序遍历

利用栈的特性，采用两个栈来实现： 栈1，存放偶数层节点 栈2，存放奇数层节点 栈1出栈的时候，将下一层节点push到栈2，这样就实现了不断反转的效果。 有一个至关重要的细节：对栈2出栈并将下一层节点推入栈1的过程中，需要先入右节点再入左节点，否则无法保证顺序。这个特性可以借助例子推导一下。 // // Created by jt on 2020/8/22. // #include <vector> #include <stack> using namespace std; class Solution { public: /** * ...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-08-22 01:06

华中科技大学 C++

二叉树的最大深度

本题有多种解法： 后序遍历，每次返回以当前节点为根节点的子树的深度 先序遍历，记录根节点到当前节点的高度，如果是叶子，则更新max值 下面采用第一种思路： class Solution { public: /** * * @param root TreeNode类 * @return int整型 */ int maxDepth(TreeNode* root) { // write code here return postOrder(root); } int postOrder(Tre...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-08-22 00:57

华中科技大学 C++

根据前序遍历和中序遍历构建二叉树

采用先序遍历的思想构建即可。 编码过程中，遇到了一个bug，只能通过25%的样例，反复检查逻辑问题，没有什么差错，最后面发现，原来是把第36行的==写成了=2333。总结：定位bug需要从多方面考虑： 如果是样例通过不了：考虑算法思路是否有误、运算符是不是写错了 如果是编译错误：考虑语法问题 如果是段错误、溢出：考虑边界问题，尤其是指针和数组下标 // // Created by jt on 2020/8/21. // #include <vector> using namespace std; struct TreeNode { int val; stru...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-08-22 00:27

已编辑

华中科技大学 C++

通过中序遍历和后序遍历构造二叉树

思路很容易想，但是能不能顺利写出代码来又是另外一回事。 一共提交了16次才成功，我的妈啊。。。 为了加快编码速度，防止出错，加点小总结： TreeNode* inOrder(vector<int> &inorder, int inL, int inR, vector<int> &postorder, int pL, int pR)比TreeNode* inOrder(vector<int> &inorder, vector<int> &postorder, int inL, int inR, int pL, in...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-08-21 21:15

华中科技大学 C++

二叉树自底向上层序遍历

利用递归的特性来实现： class Solution { public: /** * * @param root TreeNode类 * @return int整型vector<vector<>> */ vector<vector<int> > levelOrderBottom(TreeNode *root) { // write code here vector<vector<int> > res; if (!root...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-08-21 20:49

华中科技大学 C++

通过有序链表构建平衡二叉搜索树

思路和数组差不多，只是链表需要通过快慢指针找到中间节点： 根据题目示例，如果节点个数为偶数个，应该将中间偏右的那个作为根节点； 不需要断链，如果断链反而麻烦很多。 总结一下如何定位中间偏右（偶数个节点数）的节点以及如何定位中间偏左的节点： 中间偏右：循环条件为!fast && !fast->next 中间偏左：循环条件为!fast->next && !fast->next->next (本题需要根据上面略微修改一下) 代码如下： class Solution { public: /** * * @par...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-08-21 19:42

华中科技大学 C++

升序数组转化为平衡二叉搜索树

先序遍历。 注意一点即可，在求中点的过程中，理论上left + (right-left) / 2和left + (right - left + 1) / 2都是合法的，但从题目中的示例可以得知，我们的代码里应使用后者才能符合题意。 这有一个小插曲，刚开始我在sortedArrayToBST中写了如下代码，结果有5%的案例出现段错误，百思不得其姐，大家猜猜问题出在哪里？ TreeNode* sortedArrayToBST(vector<int>& num) { TreeNode *root; if (num.size() < 1) return roo...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-08-21 19:02

华中科技大学 C++

判断二叉树是否为平衡二叉树

后序遍历： class Solution { public: /** * * @param root TreeNode类 * @return bool布尔型 */ bool isBalanced(TreeNode* root) { // write code here if (!root) return true; bool res = true; postOrder(root, res); return res; } int postOrd...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-08-21 18:00

华中科技大学 C++

二叉树根节点到叶子节点路径和为指定值的所有路径

先序遍历，套模版就是了，没啥可解释的。 class Solution { public: /** * * @param root TreeNode类 * @param sum int整型 * @return int整型vector<vector<>> */ vector<vector<int> > pathSum(TreeNode* root, int sum) { // write code here vector<vector<int...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-08-21 17:50

华中科技大学 C++

二叉树中是否存在节点和为指定值的路径

先序遍历，套模版就是了。 class Solution { public: /** * * @param root TreeNode类 * @param sum int整型 * @return bool布尔型 */ bool hasPathSum(TreeNode* root, int sum) { // write code here if (!root) return false; return preOrder(root, sum, 0); } bool p...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-08-21 17:43

已编辑

华中科技大学 C++

填充树的next指针ii

题目要求空间复杂度为常数级别，因此不能用递归或者使用队列辅助。 如果当前层中节点的next指针已经填充完毕，那么我们很容易根据当前层去填充下一层，只需要“记住”下一层的最左侧节点，即可通过循环实现题目的目标。在这里引入哑节点记录下一层最左侧节点。 另外的话，由于题中二叉树不是满二叉树或者完全二叉树，需要用一个辅助指针记录上一个节点。 代码如下： class Solution { public: void connect(TreeLinkNode *root) { TreeLinkNode *left = root; while (left) { ...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-08-21 16:53

华中科技大学 C++

填充树的next指针

用层次遍历很好做的，但是题目要求是常数级别的空间复杂度，因此需要转换思路。 我们发现： 如果设当前层为i，且当前层所有节点的next指针都已经填充，则从第i层的最左边节点出发，可以遍历当前层； 设当前节点为第i层的第j个节点，那么很容易就能填充节点j在第i+1层的子节点的next指针 于是，产生了如下代码（如果觉得理解不了，可以画画图）： class Solution { public: void connect(TreeLinkNode *root) { if (!root) return; TreeLinkNode *left = root; ...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-08-21 16:16

华中科技大学 C++

二叉树根节点到叶子节点的所有路径数字和

毋庸置疑，用先序遍历。但是实现起来却有点问题。刚开始我用一个string类型变量保存路径上所有数字，用一个int &sum保存结果，但是只通过了95%。后面发现其实可以直接通过一个数字传递路径上数字和，遇到叶节点返回左右子树相加的结果即可。 class Solution { public: /** * * @param root TreeNode类 * @return int整型 */ int sumNumbers(TreeNode* root) { // write code here if(!r...

刷遍天下无敌手

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客企业服务