class Solution { public: //这题有两种做法。一种是暴力的中序遍历，把结果存储下来（应该是没有不存储结果就能提前在找到时返回的办法了。）然后去比对。但题目要求空间复杂度为O(1)，所以这种办法没法用。 //这种是分类法。我自己分了5类。 //1.是左孩子且是叶节点时（5），打印父节点（6）。 //2.是左孩子但不是叶节点时（6），如果有右孩子，打印右孩子。如果没右孩子，就打印父节点。 //3.是右孩子且是叶节点时（7），朝父节点进行递归（6）。 //4.是右孩子但不是叶节点,且自己的右孩子存在时（10），朝自己的右孩子进行递归（11）。 //5.若自己的右孩子不存在...

#include <stack> class Solution { public: //思路：该树节点的值比pq都小，说明pq都在右子树，比pq都大，说明pq都在左子树，处于pq之间，说明正好一左一右，该节点就是最近公共祖先。 //另外，这题也可以用题解中的路径法来做。 int solve(TreeNode* root,int p,int q) { if(root==nullptr) return -1; int val=root->val; if(val==p || val==q) ...

#include <vector> class Solution { public: //思路：虽然我们无法只靠后序遍历的结果就完整地构建出一棵树，但是既然有了二叉搜索树的这一限定条件（题目只说只要这个后序遍历的结果能满足是某一个二叉搜索树的遍历结果就行，也就是说，重点是放在符合二叉搜索树的定义，而不是构建出原本的树上），我们就只用专心于判断是否满足二叉搜索树的定义即可。 //递归地判断每一棵子树是否满足定义。 bool solve(int begin, int end, vector<int>& seq) { if (beg...

//这道题就是个层序遍历。 #include <queue> #include <vector> class Solution { public: vector<int> PrintFromTopToBottom(TreeNode* root) { vector<int>result; if(root==nullptr) return result; queue<TreeNode*>q; q.push(root); while (!q.empty()) { TreeNode *top=q.fro...

class Solution { public: //一开始我的思路是用层序遍历+一个栈来反向构造。但一看通过率这么高就觉得应该不会这么复杂。再仔细一想，把整棵树都是镜像的问题分解到最小的子树也是镜像，这样就能解决了。因此就很简单了。 TreeNode* Mirror(TreeNode* pRoot) { // write code here if(pRoot==nullptr) return nullptr; if(pRoot->left==nullptr && pRoot->right==nullp...

//这道题的思路，看到判断B是不是A的子结构，其实就是在比较B与A的某个子树是否一致。因此在局部上，这基本是个比较两棵二叉树是否相等的问题。用solve函数正常的递归解决就行。唯一需要注意的是可以允许A戛然而止，比如A后面还有更多的孙子节点，但只要到目前为止都与B相同就行了。因此需要在solve函数中处理B==nullptr的情况。 //而在宏观上，我们需要把A的子树一个个抓出来与B做比较。找到A的所有子树其实就是遍历A树的所有节点，因此在宏观上还要再写一个前序遍历来调用solve函数。 //完。 class Solution { public: //可以将这个问题转化为求两棵树是否长得一样...

class Solution { public: stack<TreeNode*> mystack; //思路分析：这道题要求给出第k小（第k大其实也是一个道理）的数，而且是在二叉搜索数上的。由于二叉搜索数的左小右大的特性，这道题可以转化为“先遍历二叉搜索树，将树转化为一个有序的数组，最后再找到第k个即可。” //写递归的时候，边界条件：自身为空。顺序：右孩子比自己大，先入栈，自己接着入栈，最后左孩子入栈。自己入栈时直接写就行，左右孩子则递归调用。 void solve(TreeNode* proot) { if(proot...

class Solution { public:     int findShortestPath(int n, int m, vector<vector<int> >& graph) {         // write code here       &...

两种思路，层序遍历判断对称，或是直接在递归中判断。     //思路，可以用层序遍历，每一层的结果在数组中一定是镜像的。     //判断时直接在数组中预判下一层即可。     bool isSymmetrical_v1(TreeNode* pRoot) {         if(pRoot==NULL)     &nbsp...

第一版代码。44ms，7676KB     int lowestCommonAncestor(TreeNode* root, int o1, int o2) {         // write code here         if(root==NULL)   &nbsp...

第一版代码，用了栈，然后把栈拷贝后逆序复制到数组中。其实可以不用栈的，省了栈和拷贝栈的空间。能直接把数组当栈使。     stack<TreeNode*> s;     void func(TreeNode* root, int sum, vector<vector<int> >& results) {       &...

普通版的思路……时间复杂度比较高     //这道题的本质是让我们记录每一条从根到叶子的路径     //思路是用栈来做，每抵达一个叶子节点时，就把它从栈中弹出，然后访问栈顶     //看看栈顶的节点还有没有未访问过的子节点能继续加入的，没有的话就继续弹出。     //用递归做比较好，不然还得维护每个节点的两个子节点是否有被访问过。     stack<TreeNode*>&n...

重构二叉树的代码此处不多赘述。 输出右视图用的也是层序遍历，将下一层的孩子节点先都缓存到另一个队列里，等本层的父节点都处理完了再将孩子节点从缓存队列倒到新队列里来。 这样的话，主队列为空的时候，就代表本层处理完了——也就是说刚处理了本层最右边的节点。借此我们就可以得到二叉树中最右边的节点了。     vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {  &...