qiaoxu123’s gists

qiaoxu123 / pointer.cpp

Last active January 2, 2019 00:58

> 该问题归根结底是链表的遍历问题 - 第一种方法：使用set数组存储遍历过的地址，然后每次到了新节点都搜索下有没有经过这个节点（复杂度太高） >在遍历类题目中经常可见，慢慢学习记忆。 - 第二种方法：比较巧妙。使用快慢指针来实现，如果二者相遇，则说明存在环。

	//Runtime: 8 ms, faster than 66.59%

	class Solution {
	public:
	bool hasCycle(ListNode *head) {
	ListNode *fast = head;
	ListNode *slow = head;

	while(fast && fast->next){
	slow = slow->next;

qiaoxu123 / test1.cpp

Last active January 2, 2019 01:46

> 考察二叉搜索树的性质及遍历 - 常规方法，遍历，然后相加即可。值得注意的是，先遍历右边的子树（二叉查找树的性质决定的，可以把大的数先累加起来到根节点上）会更方便和好理解。

	//Runtime: 40 ms, faster than 36.67%

	class Solution {
	public:
	int curSum = 0;

	void travelBST(TreeNode* root){
	if(!root) return;
	if(root->right) travelBST(root->right);

qiaoxu123 / myCode.cpp

Last active January 3, 2019 00:56

> 很简单一道题目，自己写的虽然陋不过也实现了，后面根据discuss完善一下。 - 算法1：递归判断即可 - 算法2：使用set数组的特性，最后判断set数组的大小即可

	//Runtime: 4 ms, faster than 91.80%

	class Solution {
	public:
	int temp;
	bool flag = true;

	bool isUnivalTree(TreeNode* root) {
	if(!root) return NULL;
	temp = root->val;

qiaoxu123 / myCode.cpp

Last active January 4, 2019 13:28

> 二叉树前序遍历，两种思路： - 递归 - 栈

	//Runtime: 0 ms, faster than 100.00%

	#include <ios>
	static auto fastInput = []() {
	ios_base::sync_with_stdio(false),cin.tie(nullptr);
	return 0;
	}();

	class Solution {
	public:

qiaoxu123 / iterative.cpp

Last active January 5, 2019 01:48

> 二叉树的中序遍历经过查找，遍历存在着三种方法，在这汇总整理下。 - Recursive solution : O(n) time and O(n) space - Iterative solution using stack : O(n) time and O(n) space - Morris traversal : O(n) time and O(1) space > 可参考这篇[博客](https://www.cnblogs.com/AnnieKim/archive/201

	//Runtime: 0 ms, faster than 100.00%

	class Solution {
	public:
	vector<int> inorderTraversal(TreeNode* root) {
	vector<int> nodes;
	stack<TreeNode*> todo;
	TreeNode* cur = root;
	while(cur \|\| !todo.empty()){
	if(cur){

qiaoxu123 / myCode.cpp

Created January 4, 2019 01:00

类似前序和中序，只是读取节点值的顺序不同而已

	//Runtime: 0 ms, faster than 100.00%

	#include <ios>
	static auto fastInput = []() {
	ios_base::sync_with_stdio(false),cin.tie(nullptr);
	return 0;
	}();

	class Solution {
	public:

qiaoxu123 / queue.cpp

Last active January 7, 2019 01:02

> 对称二叉树的判断进一步考察对二叉树的了解，方法有递归形式和非递归形式 - Approach 1 ： recursive > 改变递归遍历的次序，从而进行对称的比较 - Approach 2 ： queue > 使用队列进行存储，进行宽度优先比较

	//Runtime: 8 ms, faster than 39.55%

	class Solution {
	public:
	bool isSymmetric(TreeNode* root) {
	TreeNode* t1, *t2;
	queue<TreeNode*> q;
	q.push(root);
	q.push(root);
	while(!q.empty()){

qiaoxu123 / depth.cpp

Last active January 8, 2019 02:01

> 遍历二叉树题目，有点难，需要对二叉树的递归遍历有很深的理解，还是有很多地方不到位啊。 - Approach 1 ： recursive > 使用遍历进行比较 - Approach 2 ： depth compare + recursive > 首先判断两棵二叉树的深度，然后再递归判断，减少运算量

	//Runtime: 28 ms, faster than 30.42%

	class Solution {
	vector<TreeNode*> nodes;
	public:
	bool isSubtree(TreeNode* s, TreeNode* t) {
	if(!s && !t) return true;
	if(!s \|\| !t) return false;

	getDepth(s,getDepth(t,-1));

qiaoxu123 / myCode.cpp

Last active January 9, 2019 03:57

> 考察链表遍历由于链表的特性，访问只能顺序访问。 - Approach 1 ： Array > 如果考虑额外空间，可以使用数组存储后然后头尾对照判断，和字符串的判断基本相同。 - Approach 2 : recursive > 通过递归的形式进行比较

	//20ms 50%

	class Solution {
	public:
	bool isPalindrome(ListNode* head) {
	if(!head \|\| !head->next)
	return true;
	vector<int> array;
	array.push_back(head->val);
	while(head->next != NULL){

qiaoxu123 / iterative.cpp

Last active January 10, 2019 13:57

> 考察二叉树的搜索查找。难度不大。需要注意的是，利用二叉搜索树的特性来做，会更快一些 - Approach 1：pair > 使用pair数组记录数值大小还有结点的地址，如果大小相同则返回 - Approach 2 : iterative > 递归和想象中一样简单，只是不敢尝试罢了

	// 36 ms

	TreeNode* searchBST(TreeNode* root, int val) {
	while (root != nullptr && root->val != val) {
	root = (root->val > val) ? root->left : root->right;
	}
	return root;
	}

xqiao qiaoxu123