1.求二叉树的最近公共祖先：

        原题链接：. - 力扣（LeetCode）

        假设这题的p，q分别为7和8，而它们的最近公共祖先肯定是为3。

这题我们大致的思路为保存p，q的绝对路径，接着通过存储的绝对路径去寻找第一个相同的节点假设公共节点。

        1.1：寻找7节点：

        

                1.2：8节点也是同样的方式进行：

        1.3：找到最近的公共节点

                

        代码：

class Solution {
public:bool Find(TreeNode* root,TreeNode* val,stack<TreeNode*>&st){if(!root)return false;st.push(root);if(root==val)return true;if(Find(root->left,val,st))return true;if(Find(root->right,val,st))return true;//如果此时的节点的根，左子树，右子树都没有找到val，就说明val并不在这个节点，将这个节点pop掉。st.pop();return false;        }TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){//1.使用两个栈用来保存p，q的绝对路径//2.接着pop较长的栈，保持两个栈相等//3.两个栈同时pop，最终得到相等的就是祖先stack<TreeNode*> st1;stack<TreeNode*> st2;Find(root,p,st1);Find(root,q,st2);while(st1.size()>st2.size())st1.pop();while(st2.size()>st1.size())st2.pop();while(st1.top()!=st2.top()){st1.pop();st2.pop();}return st1.top();}
};

2.二叉搜索树与双向链表

        原题链接：二叉搜索树与双向链表_牛客题霸_牛客网

        其实这题如果忽略题目要求就很简单，因为是标准的搜索二叉树，就通过中序遍历存入list题目就解决了，但小编应题目要求，空间复杂度为O(1)及在原树上操作。本题需要对递归有一定的理解才方便做。

        

        这里小编要提出一个穿越者思想，及把自己想象成一个可以穿越时间的人，而二叉树有left和right与根。将left想象成昨天，将right想象成明天。因为是搜索二叉树所以必然会走一个中序遍历，所以我们将在中序遍历上进行操作。

        条件1：我们知道昨天发生什么

        条件2：我们虽然不知道明天将发生什么，但我们穿越到明天后再回到今天就能知道明天发生什么。

        

        这里小编想多一嘴，为什么cur会回到6节点，因为我们采用的方式是递归，递归函数会进行压栈，当我们压入4节点的函数栈帧时候，6节点栈帧会保存在4节点下面，而当4节点函数结束时候，此时函数栈帧进行弹出销毁，6节点就是栈顶，所以此时cur的值就是6.而且因为递归的关系，就算指向改变了也不会影响中序遍历的顺序，因为已经将顺序全部压入栈中了。

                

        代码：

class Solution {
public:bool TrainsTree(TreeNode*&prev,TreeNode*cur){if(cur==nullptr)return false;TrainsTree(prev,cur->left);cur->left=prev;if(prev)prev->right=cur;prev=cur;TrainsTree(prev, cur->right);return true;}TreeNode* Convert(TreeNode* pRootOfTree){TreeNode*prev=nullptr;TrainsTree(prev, pRootOfTree);TreeNode*head=pRootOfTree;while (head&&head->left) {head=head->left;}return  head;}
};

       代码看着很简单，就只是在改动指针之间的指向，但这就是递归的魅力，看着很简单，实际想出来很难。

3.从前序和中序遍历序列构建二叉树

        原题链接：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

        

        题目要求给定两个二叉树序列的数组，要求我们从两个序列中构建二叉树，那么我们先从画图思考如何构建。  

        代码：

class Solution {
public:TreeNode*_build(vector<int>& preorder, vector<int>& inorder,int &pi,int ileft ,int iright ){if(ileft>iright)return nullptr;//使用前序遍历思想，进来就先确定根TreeNode *key=new TreeNode(preorder[pi]);//使用中序遍历思想，找到根，区分根的左子树与右子树int keyi=0;while(keyi<inorder.size()){if(inorder[keyi]==preorder[pi])break;keyi++;}pi++;//[ileft keyi-1] keyi [keyi+1 iright];key->left=_build(preorder,inorder,pi,ileft,keyi-1);key->right=_build(preorder,inorder,pi,keyi+1,iright);return key;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder){int pi=0, ileft=0 , iright=inorder.size()-1;return _build(preorder,inorder,pi,ileft,iright);}
};

        代码递归结束条件为ileft大于iright，就好比如我们想确定9是不是属于叶子节点，在递归9的左子树时，ileft=0，iright=-1，而在递归9的右子树时候会发现ileft=1，而iright=0。这显然不是一个有效的区间所以直接退出。

4.二叉树的前序遍历

        原题链接：144. 二叉树的前序遍历 - 力扣（LeetCode）

        可能看到这有读者疑惑，这题不是很简单吗，为啥还需要拿出来讲。是的这题使用递归的思想就是很简单，但如果要求采用的是非递归的方式呢？应该怎么做

        

        

        假设我们需要前序遍历这颗子树应该怎么遍历呢？

        

        因为是前序遍历，所以我们在一开始遍历根的时候直接将值存入vector中，在将节点压入栈中。

        这里主要的核心是通过栈的先进先出的特性来模拟递归遍历的过程，当我们的cur指针只需要一直往左子树遍历。用栈去存储节点，当cur指向空的时候表明该根的左子树已经遍历完成，接着弹出栈顶节点，如果栈顶节点没有右节点就不用管，继续弹出下一个栈顶节点，而如果弹出的栈顶节点有右子树，那么我们就重新让cur指向我们弹出节点的右节点，接着继续遍历入栈循环。直到栈为空与cur指向为空，就表明该子树全部遍历完成了。

        代码：

    vector<int> preorderTraversal(TreeNode* root){vector<int> vv;stack<TreeNode*> st;TreeNode *cur=root;TreeNode *temp=nullptr;while(cur||!st.empty()){if(cur){vv.push_back(cur->val);st.push(cur);cur=cur->left;}else{temp= st.top();st.pop();cur=temp->right;  }}return vv;}

        

5.二叉树的后序遍历

        原题链接：145. 二叉树的后序遍历 - 力扣（LeetCode）

        这题我们就以这颗二叉树为例，我们直到后序遍历为:左子树|右子树|根 而很显然在后序遍历的时候根节点会被访问两次,所以这题我们会两次访问根节点,而难点在于我们并不知道我们的右子树是否已经访问过了.

                

        代码:

 vector<int> postorderTraversal(TreeNode* root){vector<int> vv;stack<TreeNode*> st;TreeNode *cur=root;TreeNode *temp=nullptr;TreeNode*prev=nullptr;while(cur||!st.empty()){while(cur){st.push(cur);cur=cur->left;}//后序遍历二叉树会走两次根节点，//如果一个根的右节点没被访问，那么访问根的前一个节点为根的左子树//如果一个根的右子树被访问了，那么访问根的前一个节点为根的右子树temp=st.top();if(temp->right==nullptr || prev==temp->right){vv.push_back(temp->val);st.pop();prev=temp;}else{cur=temp->right;}}return vv;}

                                

                                                                                                那么本片文章到这里就结束了,感谢各位观看,如果觉得对您有帮助,还请点点赞