大的方面来讲，根据节点在树中所处的位置，分成三种情况： 1. 节点自己就是根节点 此时看其右节点：  右节点为空，返回空 右节点不空且没有左子节点，返回右节点 右节点有左子节点，返回其最左边的子节点  2. 节点是某个节点的左子节点 比较简单两种情况：  如果它有右子节点，返回右子节点 如果没有右子节点，返回父节点  3. 节点是某个节点的右子节点 需要考虑其父节点的情况分类讨论  如果它有右子节点，返回右子节点 看其父父节点，不存在，返回空 父父节点存在，父父左是其父，返回父父节点 否则，一直向上找，直到满足上面2、3中两种情况之一  /* struct TreeLinkNode { int...

递归实现DFS。 需要注意，输入的val可能是负的，节点值也可能是负的，所以只有到了leaf node之后才能判断值是否已经符合条件了， 中间不能按照大小判断。 /* 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> > FindPath(TreeNode* root,i...

后序遍历二叉树的性质是，根节点肯定在最后。这样就为递归解决提供了可能。 找到根后，从左往后走，小于根的是左子树，大于根的是右子树。注意：如果右子树中出现了小于根的数，那就判否了。 细节方面，需要主要几个特例：如size=0,1,2，怎么处理？0=false，1/2=true。  class Solution { public: bool VerifySquenceOfBST(vector<int> sequence) { if(sequence.empty()) return false; int size = sequence.size(); if(1==size) return...

本质BFS，可以使用递归实现，使用vector保存每一层的nodes。 但需要注意之字形相邻层顺序相反，所以用一个标志位实现。 另外，使用std::reverse_iterator实现逆向遍历vector，也可以使用std::reverse函数。  /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: vector<vec...

比较容易想到，但不容易写对:) 我的思路是，既然对链表做了修改，就索性新建一个，把符合条件的节点拷贝出来。所以问题就成了怎么找到符合条件的节点？ 很明显，需要用到至少两个指针，用来判断相邻两个节点的值是否相等。然后设置一个标志位，保存上次判断相邻两个节点值相等的状态，然后向下遍历，每次不断更新和判断这个标志位，如果满足题目要求就拷贝出来。 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: List...

最笨最直接的方法：  根据next指针将链表的label值拷贝出来生成新的链表pNode。 两个链表同时遍历，填充random   每一个元素，内部再两个链表同时遍历 找到第一个的random时，第二个链表也指向正确的random，此时赋值给第二个的random 注意几个特殊情况：random指向空，random指向自己  本方法的时间复杂度O(n+n^2) = O(n^2);空间复杂度O(1) /* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : ...

class Solution { public: int rectCover(int number) { if(number < 1 ) return 0; if(number == 1) return 1; if(number == 2) return 2; return countCore(number, 1, 2); } int countCore(int n, int n1, int n2){ if(n == 2) return n2; return countCore(n-1, n2, n2+n1); } }; 从number0开始分析：    number method   ...

class Solution { public: int jumpFloorII(int number) { if(number == 1) return 1; if(number == 2) return 2; int n1 = 1, n2 = 2; int rt = 0; int sum = n1 + n2; for(int i=3; i <= number; ++i){ rt = sum + 1; sum = rt + sum; } return rt; } }; 递推分析，但用for loop 完成。 f(n) = f(n-1) + f(n-2) + ... + f(1) + 1...