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;
}
那么本片文章到这里就结束了,感谢各位观看,如果觉得对您有帮助,还请点点赞
