二叉树的相关题目

目录

1、根据二叉树创建字符串

2、二叉树的层序遍历

3、二叉树的最近公共祖先

 4、搜索二叉树与双向链表

 5、从前序与中序遍历序列构造二叉树

6、 从中序与后序遍历序列构造二叉树

7、二叉树的前序遍历（非递归实现）

8、二叉树的中序遍历（非递归实现）

9、二叉树的后序遍历（非递归实现）

---

1、根据二叉树创建字符串

题目要求：给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。

---

例1：

 前序遍历完应该是"1(2(3)())(5)"，但是2没有右孩子，所以可以省略第一个括号

化简为："1(2(3))(5)"

---

例2：

  前序遍历完应该是"1(2()(3))(5)"，但是2没有左孩子，如果省略第一个括号，会辨别不清是左孩子还是右孩子

所以依旧为："1(2()(3))(5)"

---

根据上面的样例，可以明白有这样几种情况：
①左右都不为空，则都不省略括号
②左右都为空，都省略括号
③左不为空，右为空，可以省略右括号
④左为空，右不为空，不能省略左括号
总结就是：如果右不为空，无论左边是否为空，右边都需要加括号
如果左不为空或右不为空，则左边需要加括号

代码如下：

class Solution {
public:string tree2str(TreeNode* root) {//若root为空，则返回一个string的匿名对象if(root == nullptr){return string();}//1、如果左不为空或右不为空，左边需要加括号//2、如果右不为空，右边需要加括号string str;//to_string将val转换为字符变量，以便可以+=str += to_string(root->val);//情况1if(root->left || root->right){str += '(';str += tree2str(root->left);str += ')';}//情况2if(root->right){str += '(';str += tree2str(root->right);str += ')';}return str;}
};

---

2、二叉树的层序遍历

 题目要求：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

---

思路分析：

我们可以创建一个队列，队列中存的是二叉树的指针，再给一个levelSize，记录每一层的节点数，在循环过程中，创建一个vector<int>的数组，存每一层的结点val值。首先，二叉树若不为空则将root存进队列中，再经过判断将root的左右孩子存进队列中，队列头结点pop前，都将val存入v中，每层结束，都将v的值push_back到vv中，以此类推，具体代码中注释部分有

---

代码：

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {//层序遍历一般会使用队列queue<TreeNode*> q;//levelSize是每一层的节点数size_t levelSize = 0;//如果根节点不为空，则队列中插入root，节点数置为1if(root){q.push(root);levelSize = 1;}//vv是需要返回的vector<vector<int>>vector<vector<int>> vv;//while循环，直到队列为空while(!q.empty()){//创建vector<int> v，存储每一层的结点的valvector<int> v;//for循环保证每次循环一层的结点for(size_t i = 0;i < levelSize; ++i){//由于每次都要删除队列的第一个值//所以front来保留一下指针，以免找不到左右字树TreeNode* front = q.front();q.pop();//每次删除的时候都存进vv.push_back(front->val);//如果删除结点有左右孩子，都存进队列中if(front->left)q.push(front->left);if(front->right)q.push(front->right);          }//每循环完一层，就往vv里存一层的val值vv.push_back(v);//接着重新赋值levelSize，即下一层数的节点数levelSize = q.size();}return vv;}
};

---

3、二叉树的最近公共祖先

题目要求：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

方法一例1：

 则最近公共祖先是结点2

方法一例2：

 则最近公共祖先是结点4

所以方法一我们可以用下面两个思路：

1、如果一个是左子树中的结点，一个是右子树中的结点，那么它就是最近公共祖先

2、如果一个结点A是结点B的祖先，那么公共祖先就是结点A

方法一的代码：（方法一如果遇到公共祖先在二叉树下面的部分，会导致效率比较低）

class Solution {
public:bool Find(TreeNode* root, TreeNode* x){//如果查找的为空，返回nullptrif(root == nullptr)return false;//如果找到了，返回trueif(root == x)return true;//如果没找到，则递归进左右字树找return Find(root->left, x) || Find(root->right, x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == nullptr)return nullptr;//说明公共祖先是root，if((root == p) || (root == q))return root;//p/q在一左一右，则说明当前root是公共祖先//设定4个bool类型变量，与Find结合使用bool pInLeft,pInRight,qInleft,qInRight;pInLeft = Find(root->left, p);pInRight = !pInLeft;//在左就说明不在右，所以可以用！qInleft = Find(root->left, q);qInRight = !qInleft;//一个在左一个在右，则它是公共祖先if((pInLeft && qInRight) || (pInRight && qInleft))return root;//若都在root左或右，则递归进左或右子树中，重新判断上面的条件else if(pInLeft && qInleft)return lowestCommonAncestor(root->left, p, q);else if(pInRight && qInRight)return lowestCommonAncestor(root->right, p, q);//此题不会进入这里，因为p/q都在二叉树中elsereturn nullptr;}
};

方法二思路：（相比方法一效率高点，O(N)）

将p和q的从根结点开始的路径放入栈中，将所得两个结点的较长的路径pop到和较短路径一样长为止，然后依次判断栈顶元素是否相同

思路类似链表相交

方法二例子：

结点3和结点1的路径放栈里如图：

 结点1路径长度大，pop相等后变为：

 接着从两个栈顶元素3和9开始判断，不相同，两个都pop，直到遇到2，返回结点2

方法二代码：

class Solution {
public:bool FindPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path){//是空返回falseif(root == nullptr)return false;//不论是不是先入栈，因为后面判断不是路径会poppath.push(root);//如果找到了，返回trueif(root == x)return true;//如果没找到，进入左子树找if(FindPath(root->left,x,path))return true;//如果左子树没找到，进入右子树找if(FindPath(root->right,x,path))return true;//左右字树都没找到，pop掉当前栈顶元素，返回falsepath.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//栈的每个元素都是TreeNode*类型stack<TreeNode*> pPath,qPath;//FindPath中传入的pPath和qPath都是p和q从根结点的路径FindPath(root, p, pPath);FindPath(root, q, qPath);//p/q结点的路径长度不同，先变为相同路径长度while(pPath.size() != qPath.size()){if(pPath.size() > qPath.size())pPath.pop();elseqPath.pop();}//相同路径长度一层层判断顶部元素是否相同while(pPath.top() != qPath.top()){pPath.pop();qPath.pop();       }//走到这里说明找到了相同的结点，即最近祖先return pPath.top();}
};

---

 4、搜索二叉树与双向链表

题目要求：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示：

1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构

---

思路分析：

由于不能创建新的结点，只能调整树中结点指针的指向，所以我们就不能用先中序排好序以后，再遍历的方法

那么就在中序遍历的过程中，给两个指针，一个prev，一个cur，prev是指向前一个结点，cur是值向当前的结点，每次cur变化前，都将值赋值给prev，然后再将cur->left指向prev，以此类推完成了left指针，当前的prev就是上一个cur，所以prev->right = cur就是相当于上一个cur->right也指向了下一个结点，从而完成了right指针

---

代码：

class Solution {
public://中序遍历，并在过程中调整结点指针的指向//cur是当前结点的指针，prev是前一个结点的指针void Inorder(TreeNode* cur,TreeNode*& prev){if(cur == nullptr)return;//先左子树Inorder(cur->left,prev);//cur->left直接给prev，因为prev是前一个结点指针cur->left = prev;//若prev不为空，且为TreeNode*& prev，是传引用，即：//prev->right就完成了上一个cur结点的right指针指向if(prev)prev->right = cur;//在cur指向下一个之前，赋值给prevprev = cur;//再右子树Inorder(cur->right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {//创建一个prev置空，传入Inorder进行中序排序TreeNode* prev = nullptr;Inorder(pRootOfTree, prev);//head先指定为题目所给的根结点TreeNode* head = pRootOfTree;//顺着left指针找到中序遍历的第一个结点//为了防止pRootOfTree为空，要先判断headwhile(head && head->left)head = head->left;//返回第一个结点指针return head;}
};

---

---

 5、从前序与中序遍历序列构造二叉树

题目要求：给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

 思路：

通过前序遍历确定根，通过中序遍历确定左右字树

子树区间确认是否继续递归创建子树，不存在区间则是空树

代码：

class Solution {
public://创建_buildTree函数进行递归调用//prei是前序遍历结果的首元素下标，inbegin、inend是中序遍历结果首尾元素的下标TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& prei, int inbegin, int inend){//如果在前序遍历的结果中找，if(inbegin > inend)return nullptr;//每次递归通过前序遍历结果创建根结点TreeNode* root = new TreeNode(preorder[prei++]);//while循环找到中序遍历的该结点的位置int cur = inbegin;while(cur <= inend){if(inorder[cur] == root->val)break;elsecur++;}//中序遍历的结果中，分成了三个部分，[左子树]根[右子树]//[inbegin, cur-1] cur [cur+1,inend]//所以接下来递归时，传入这两个区间root->left = _buildTree(preorder,inorder,prei,inbegin,cur-1);root->right = _buildTree(preorder,inorder,prei,cur+1,inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {//前序遍历首元素下标为0int prei = 0;//中序遍历结果首尾元素的下标为0和inorder.size()-1TreeNode* root = _buildTree(preorder,inorder,prei,0,inorder.size()-1);return root;}
};

---

---

---

6、 从中序与后序遍历序列构造二叉树

题目要求：给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

---

这个题和上面的从前序与中序遍历序列构造二叉树大体思路一样，但是由于是后序确定根结点，所以给定后序遍历结果的下标posi，每次都会posi--，并且是先递归右子树，再递归左子树，因为后序遍历顺序是左子树，右子树，根结点，反过来就是根结点，右子树，左子树

所以代码如下：

class Solution {
public:TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder,int& posi,int inbegin,int inend){if(inbegin > inend)return nullptr;TreeNode* root = new TreeNode(postorder[posi--]);int cur = inbegin;while(cur <= inend){if(root->val == inorder[cur])break;elsecur++;}//[inbegin,cur-1] cur [cur+1,inend]root->right = _buildTree(inorder,postorder,posi,cur+1,inend);root->left = _buildTree(inorder,postorder,posi,inbegin,cur-1);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int posi = postorder.size()-1;return _buildTree(inorder,postorder,posi,0,inorder.size()-1);}
};

---

---

7、二叉树的前序遍历（非递归实现）

题目要求：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

---

思路分析：

采用非递归实现该问题，能提高效率，并且递归调用需要建立栈帧，如果深度比较深会容易崩溃，所以需要掌握非递归的方法

前序遍历中，我们可以将所有结点分为左路结点，以及左路结点的右子树

那么我们第一步就是将左路结点都保存下来，并且存在栈中，接着将存入栈的结点一个一个出栈，并访问右子树，然后重复上面的步骤（左路结点保存，入栈，全部入栈后，然后出栈，访问该出栈结点的右子树）

当左路结点从栈中出来时，表示左子树以及访问过了，该访问该结点和它的右子树了

就相当于转换为了子问题，将所有结点分为左路结点，以及左路结点的右子树，接着将左路结点的右子树又分为：左路结点，以及左路结点的右子树以此类推，从而实现非递归的方法完成前序遍历

---

代码如下：

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*> st;TreeNode* cur = root;//循环条件有两个都不符合才结束循环//一是栈里空，表明初始的左路结点的右子树都已访问//二是cur为空，表明访问的栈中的结点的右子树为空while(cur || !st.empty()){//1、左路结点while(cur){v.push_back(cur->val);st.push(cur);cur = cur->left;}//2、左树结点的右子树TreeNode* top = st.top();st.pop();//将左路结点以外的数转化为上面两条的子问题//转换为子问题从而访问栈中结点的右子树cur = top->right;}return v;}
};

---

---

8、二叉树的中序遍历（非递归实现）

题目要求：给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

---

中序遍历和前序遍历思路大体相同，但是由于中序遍历是：左子树，根，右子树。所以中序遍历的结果需要在左路结点都入栈后，再依次push_back进数组中，剩下思路和前序遍历相同

---

代码如下：

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*> st;TreeNode* cur = root;while(cur || !st.empty()){while(cur){st.push(cur);cur = cur->left;}//左路结点都入栈后，再尾插栈顶元素到数组中//依次取栈顶元素，再pop，转换为子问题循环TreeNode* top = st.top();   st.pop();v.push_back(top->val);cur = top->right;}return v;}
};

---

---

9、二叉树的后序遍历（非递归实现）

题目要求：给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

---

思路分析：

后序遍历和前序/中序有一点区别，因为后序是左子树，右子树，根，我们先找到左路结点后，无法确认该结点的右子树有没有访问，所以就这一问题可以分类讨论

设定一个prev结点，让他指向cur结点的前一个结点，即每次尾插入数组时都记录当前的结点值，赋值给prev，这样在cur = cur->right以后，prev就是cur所访问的前一个结点。

将所有左路结点全部插入到栈以后，分为两种情况：

第一：该结点的右子树为空或该结点的右子树已经访问过了，第二：该结点的右子树没有被访问过

第一种情况就可以访问这个栈顶结点，否则先访问该结点的右子树，转换为了子问题

---

代码：

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*> st;TreeNode* cur = root;TreeNode* prev = nullptr;while(cur || !st.empty()){//左路结点入栈while(cur){st.push(cur);cur = cur->left;}TreeNode* top = st.top();//右子树为空或上一个访问的就是该结点的右子树的根//说明右子树已经访问过了if(top->right == nullptr || top->right == prev){v.push_back(top->val);prev = top;cur = nullptr;st.pop();}//否则先访问栈顶结点的右子树else{cur = top->right;}}return v;}
};

---

相关题目列举这些

---