思路： 利用栈的先入后出的特性，用一个元素为字符串的栈将字符串依据空格拆分出的单词先入栈再出栈即可； 代码如下： class Solution { public: string ReverseSentence(string str) { stack<string> stk; int sz=str.size(); string ret=""; for(int i=0;i<sz;++i){ string stmp=""; while(i<sz && str[i]!=' '){ stmp+=str[i]; ++i; } if(stmp!=""){ stk.pu...

思路： 第一想法就是：依次从左往右遍历两个数组来维护一个栈；  遍历入栈数组时判断当前元素值是否等于出栈元素当前值：   若相等则栈出栈，并且两个数组均向右移动到下一个元素； 若不相等则栈入栈当前入栈数组元素，入栈数组向右移动到下一个元素； 这样就模拟出了栈出入栈的过程，当遍历结束后，只要判断维护的栈是否是空的即可得到结果。  代码如下： class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { int psz=pushV.size(); int posz=popV.si...

利用队列+对每一层求节点数目  代码如下：  class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { vector<vector<int>> ret; if(pRoot==nullptr) return ret; queue<TreeNode*> que; que.push(pRoot); while(!que.empty()){ int sz=que.size();//对每一层遍历求节点数目大小 vector<int> tmp; whi...

方法一：迭代解法（利用队列） 思路： 考虑bfs中，队列的特性，可以每次出队两个节点、入队两个节点，为了方便起见，根节点首先入队两次即可.  代码如下：  class Solution { public: bool isSymmetrical(TreeNode* pRoot) { if(pRoot==nullptr) return true; queue<TreeNode*> que; que.push(pRoot);que.push(pRoot); while(!que.empty()){ TreeNode* node1=que.front(); que.pop(); TreeN...

中序遍历的性质 思路： 考虑将中序遍历当前节点的下一个节点情况分为：  右子树存在时，中序遍历右子树根节点即可得下一个节点，此时明显又可以分为：   (1)当右子树根节点不存在左子树时，则右子树根节点即为所找的节点； (2)当右子树根节点存在左子树时，中序遍历右根节点时找到的第一个叶子节点即为所找节点;   当右子树不存在时，则可以分为：   当前节点为根节点（next指针为NULL）时，由于不存在右子树，则下一个节点为NULL； 当前节点是父节点的左孩子时，由于不存在右子树，则下一个节点为当前节点的父节点； 当前节点是父节点的右孩子时， 注意此时明确的是：如果当前节点向上的所有父节点均是各自...

中序遍历+链表操作 思路： 考虑到BST树的左孩子节点小于根节点，右孩子节点大于根节点，因此中序遍历BST树时，节点即可排序；因此在生成双向链表时，总是维护一个尾指针（保存当前遍历的最后一个节点），下次遍历时让当前节点的左指针指向尾节点，让尾节点的右指针指向当前节点即可 class Solution { public: void dfs(TreeNode* pRoot,TreeNode*& pLast){//传pLast指针的应用，保存遍历的最后一个节点 if(pRoot==nullptr) return ; TreeNode* pCurrent=pRoot; if(pCurrent-...

递归+回溯 思路： 与（一）一样，也可以用递归加回溯。考虑深度优先递归前序遍历每一条路径，路径上的值依次累加并且依次保存到一个vector中，这样，当累加值等于目标值得时候（且当前节点是叶子节点时），就将此时的vector存下来；另外无论是否与目标值，在遍历完一条路径后都应该回溯（即将累加值减去当前节点值，并且从当前vector末尾删除当前值），将所有路径遍历完即获得结果。 class Solution { public: void dfs(TreeNode* root,int& get,int expectNumber,vector<int>& tmp,vecto...

递归+回溯 思路： 与大部分解法一样，考虑用前序遍历，遍历任意一条路径到叶子节点并记录路径上的和，如果此时和与目标结果相等则找到满足要求的路径，返回true即可，否则遍历完所有路径也没有找到的满足条件的话，返回false；  值得注意的是，必须是从父节点到叶子节点，因此，在找到与目标结果相等的结果时，必须判断当前是否为叶子节点； 另外，在搜索完一条从父节点到叶子节点的路径，且不满足目标值则须回溯，即减去当前节点值。  代码如下： public: bool dfs(TreeNode* root,int& get,int sum){ get+=root->val;//累加路径上的值 ...

和书上的方法一样，只是在递归时，可以不传入初始化新的向量（书上是传的指针） public: bool VerifySquenceOfBST1(vector<int> sequence,int sz) { int rootval=sequence[sz-1];//末尾是根节点 int i; for(i=0;i<sz-1;++i){ if(sequence[i]>rootval) break; } int j=i; for(;j<sz-1;++j){ if(sequence[j]<rootval) return false;//基本思路都一样，先找到递归分界点，...