strykyr - 个人主页动态

2022-01-22 17:28

dfs+剪枝 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @param sum int整型 * @return bool布尔型 */ bool flag = false; bool hasPathSum(TreeNode* root, int su...

0 点赞评论收藏

2022-01-22 17:05

中国科学技术大学 Java

题解 | #二叉搜索树的后序遍历序列#

判断是否后序遍历 情况： 全右子树 全左子树 左右子树 右左子树（此时不是后序遍历false） class Solution { public: bool VerifySquenceOfBST(vector<int> sequence) { if(sequence.size() == 0)return false; if(sequence.size() <= 2)return true; int n = sequence.size();//要么全左子树，要么全右，要么左右。 i...

0 点赞评论收藏

2022-01-22 15:58

中国科学技术大学 Java

题解 | #从上往下打印二叉树#

层序遍历 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: vector<int> PrintFromTopToBottom(TreeNode* root) { vector<int> v; queue<TreeNode*> q; ...

0 点赞评论收藏

2022-01-22 15:42

中国科学技术大学 Java

题解 | #二叉树的镜像#

二叉树镜像 思路：根据树先序遍历（根左右），建立（根右左）的树即可. /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @par...

0 点赞评论收藏

2022-01-22 15:33

中国科学技术大学 Java

题解 | #树的子结构#

树的子结构 先分析临界情况（递归的结束）； A,B任何为空即放回false A，B根节点值不等时，判断A的左子树和B || A的右子树和B A和B根节点值等时，又分情况 B左右为空，即是子树返回真。 B都不为空时判断 A左子树B左子树 && A右子树B右子树 B左不为空，判断 A左子树B左子树 B右不为空，判断 A右子树B右子树 就算A，B值当前根节点相等，仍然B可能不匹配A，即再 || 上A左子树B || A右子树B 有一真即真 /* struct TreeNode { int val; struct TreeNode *left; struc...

0 点赞评论收藏

2022-01-22 14:08

中国科学技术大学 Java

题解 | #重建二叉树#

根据先序和中序建立二叉树（评论区大佬题解c++版） 解题思路： 二叉树的前序遍历：根左右；中序遍历：左根右 由前序遍历知道根节点之后，能在中序遍历上划分出左子树和右子树。分别对中序遍历的左右子树递归进行这一过程即可建树。 图解： /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; ...

0 点赞评论收藏

2022-01-21 20:37

中国科学技术大学 Java

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

二叉搜索树的第k个节点 中序遍历变形，直接中序遍历建立数组，直接取 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @para...

0 点赞评论收藏

2022-01-21 20:19

中国科学技术大学 Java

题解 | #按之字形顺序打印二叉树#

之字形打印二叉树（层序遍历变形） 偶数层时反转即可 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { vector<...

0 点赞评论收藏

2022-01-21 19:26

中国科学技术大学 Java

题解 | #二叉树的深度#

树的深度 深搜解法。 首先判定临界条件（深搜终止条件）放回为0，然后二叉树有左右两条路，求最大的那条加上本身根节点非空的深度（1）； 如图：开始为1，非空求左树最大深度和右树最大深度的最大值+本身1； TreeDepth(pRoot->left)时：到节点2，同理左右树最大深度的最大值 + 1(本身)，右树为空即2到右树为1深度，左树同理2到4深度为 1+1 = 2；则TreeDepth(pRoot->left)最大为2 同理TreeDepth(pRoot->right)：最大为1 则根的最大深度为 max（2,1） + 1 = 3； /* struct TreeNode ...

0 点赞评论收藏

2022-01-21 19:10

中国科学技术大学 Java

题解 | #删除链表的节点#

简单的链表删除 /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @param val int整型 * @return ListNode类 ...

0 点赞评论收藏

2022-01-21 19:03

中国科学技术大学 Java

题解 | #删除链表中重复的结点#

重复节点删除 方法一：哈希表记录遍历一次，再遍历一次删除重复元素 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* deleteDuplication(ListNode* pHead) { unordered_map<int,int> m; ListNode* head = ne...

0 点赞评论收藏

2022-01-21 18:04

中国科学技术大学 Java

题解 | #复杂链表的复制#

复杂链表的复制 利用哈希表记录原节点和复制链表节点间映射（通过原节点直接找到对应的复制节点）， 先建立next链表（不含random指向） 通过哈希表（遍历哈希表），根据原节点的random指向（有原节点和复制节点的映射）直接得到复制节点的random指向。 如图：建立好next指向的复制链表后，遍历哈希表。 原节点4的random指向2, 复制节点指向复制节点的2（即 m[4->random] ），因为原2节点和复制节点2映射。 /* struct RandomListNode { int label; struct RandomListNode *next,...

0 点赞评论收藏

2022-01-21 17:17

中国科学技术大学 Java

题解 | #链表中倒数最后k个结点#

链表倒数k节点 两个指针，一个移动k次，然后一起移动。 /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pHead ListNode类 * @param k int整型 * ...

0 点赞评论收藏

2022-01-21 17:12

中国科学技术大学 Java

题解 | #链表中环的入口结点#

链表中的环 第一种：快慢指针解决环问题 快指针一次移动两次，慢指针一次移动一次，判断条件为快慢指针相遇，如果快指针为空（表示没环）如果相遇则有环，则快指针指向初试，然后快慢指针每次移动一次，直到相遇即环入口。 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead)...

0 点赞评论收藏

2022-01-21 16:46

中国科学技术大学 Java

题解 | #两个链表的第一个公共结点#

两个节点的第一个公共节点 思路：既然是公共享有的节点，必然最后公共节点同即结尾是一样的（公共节点），找到最短的链表，长链表移动到和短链表一样长的位置，同时遍历，判断即找到。 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { i...

0 点赞评论收藏

关注他的用户也关注了：