前言
在看这篇文章前希望大家是学过二叉树的，不然理解起来可能会比较费劲，但我会尽自己的努力让大家学会这些题（都是往年大厂必考题哦~）,本次一共包含了12道二叉树的OJ题，力扣与牛客网都有，大家要做的话直接点我发的链接即可。
一、稍微简单一点的二叉树OJ题
第一题：根据二叉树创建字符串
力扣链接：力扣
要求：
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
从题目要求我们可以了解到，此题分为三种情况：1.当左子树不为空，右子树为空。这个时候左子树的括号不能省略，右子树的括号可以省略 2.当左子树为空，右子树为空。这个时候为了不破坏输入与输出一一映射的关系，所以不能省略左子树的括号，参考第二个例子。3.左子树为空，右子树也为空，括号都可以省略。下面我们照着这个思路编写代码：
class Solution { public: string tree2str(TreeNode* root) { if (root==nullptr) { return ""; } string str; str+=to_string(root->val); if (root->left||root->right) { str+='('; str+=tree2str(root->left); str+=')'; } if (root->right) { str+='('; str+=tree2str(root->right); str+=')'; } return str; } };
首先我们可以看到函数的返回值是个字符串，所以如果递归的这个节点为空，那么我们要返回一个不影响结果的字符串，所以我们返回空串。然后定义一个字符串对象，一旦走到这里说明root肯定不为空，那么我们就在字符串中把节点的val加上，在这里用整形转字符串函数将val转为字符串。然后就到判断条件了，经过我们刚刚的分析，当左子树不为空我们要加括号，当左子树为空右子树不为空我们也要给左子树加上括号（为了不破坏关系），所以当左树不为空或者左树为空右树不为空我们就加上括号，左树右树都为空就不进入循环了所以肯定没有括号，我们先加左括号然后递归这棵树的左子树，直到左子树都递归完才加上右括号，即使左子树为空右子树不为空的时候，也会先加左括号然后递归一个空字符串在加上右括号。然后我们在判断右子树，如果右子树不为空就加上括号同理要递归右子树。然后我们返回结果即可。递归图如下：
第二题：二叉树的层序遍历
力扣链接：力扣
题目要求：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
层序遍历大家应该不会陌生，由于返回的是一个二维数组所以我们需要每次遍历完一层把这一层的节点放到向量中，所以需要两个栈配合才能完成遍历，下面我们直接上代码：
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> vv; if (root==nullptr) { return vv; } stack<TreeNode*> st; stack<TreeNode*> st2; st.push(root); while (!st.empty()) { int sz = st.size(); vector<int> v; for (int i = 0;i<sz;i++) { TreeNode* tmp = st.top(); st.pop(); v.push_back(tmp->val); if (tmp->left) { st2.push(tmp->left); } if (tmp->right) { st2.push(tmp->right); } } vv.push_back(v); while (!st2.empty()) { st.push(st2.top()); st2.pop(); } v.clear(); } return vv; } };
首先判断根节点是否为空，如果为空我们就返回一个二维数组。然后用两个栈，一个是当前层，一个保留下一层，首先先入根节点，进入循环后我们一定要记录栈的大小，然后用一个一维数组保存每一层的值，我们用一个循环来确定树中当前层的个数，每次出栈时都需要判断栈顶元素是否有左右子树，如果有就保存到另一个栈中供下次使用，当循环结束后就将一层的数据尾插到二维数组中，这个时候我们就该将保存的下一层的节点放到用于遍历的栈中，最后可以将一维数组清空也可以不清空，因为每次进入循环都会重新开一个一维数组，整体大循环的条件就是看用于遍历的那个栈是否为空，下面我们画一个示意图：
第三题：二叉树的层序遍历II
力扣链接：力扣
题目要求：
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
看到这道题不知道大家有没有什么想法呢？这不就是把我们刚刚层序遍历的那个二维数组逆置了一下吗，我们直接上代码：
class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> vv; if (root==nullptr) { return vv; } stack<TreeNode*> st; st.push(root); //queue<TreeNode*> q; stack<TreeNode*> st2; while (!st.empty()) { int sz = st.size(); vector<int> v; //在遍历栈的时候要注意，在循环出栈的时候会影响循环的次数，所以应该先 //提前保存栈的size，循环用保存的这个变量 for (int i = 0;i<sz;i++) { TreeNode* tmp = st.top(); st.pop(); v.push_back(tmp->val); if (tmp->left) { st2.push(tmp->left); } if (tmp->right) { st2.push(tmp->right); } } vv.push_back(v); while (!st2.empty()) { st.push(st2.top()); st2.pop(); } v.clear(); } reverse(vv.begin(),vv.end()); return vv; } };
没错！我们直接将这个二维数组逆置就是这道题的答案。
第四题：二叉树的最近公共祖先
力扣：力扣
题目要求：百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
此题有三种情况，第一种情况是当p在root的左边，q在root的右边，这种情况下root一定为公共祖先。第二种情况是：p和q都在root的左边，这种情况下需要去root的左子树递归寻找公共祖先。第三种情况是：p和q都在root的右边，这种情况下需要去root的右子树递归寻找公共祖先。
下面我们实现代码：
class Solution { public: bool isExist(TreeNode* root,TreeNode* pq) { if (root==nullptr) { return false; } if (root==pq) { return true; } return isExist(root->left,pq)||isExist(root->right,pq); } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root==nullptr) { return nullptr; } if (p==root||q==root) { return root; } bool pInleft = isExist(root->left,p); bool pInright = !pInleft; bool qInleft = isExist(root->left,q); bool qInright = !pInleft; if ((pInleft&&qInright)||(pInright&&qInleft)) { return root; } if (pInleft&&qInleft) { return lowestCommonAncestor(root->left,p,q); } if (pInright&&qInright) { return lowestCommonAncestor(root->right,p,q); } return root; } };
首先判断根节点是否为空，如果根节点都为空了那就没有找的必要了直接返回nullptr即可。然后我们发现，只要p或q之间有一个是根节点，那么公共祖先一定是根节点。然后我们判断p在root的左边还是右边，同样判断q，当p在root的左边q再root的右边或者p在root的右边，q在root的左边，这种时候root一定为公共祖先，然后当两棵树都在同一个方向时就去子树递归查找公共祖先即可。判断节点是否在一个树中的函数很简单，当root在递归的时候都为空还没找到要查找的节点这就说明这个节点不在这棵树中，当root不为空要不就是找到了要不就是去当前节点的左子树或者右子树继续查找，只要找到了就返回true。
第五题：二叉搜索树与双向链表
牛客网链接：二叉搜索树与双向链表_牛客题霸_牛客网
题目要求：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
4.你不用输出双向链表，程序会根据你的返回值自动打印输出
这道题有很多种解法，但是由于题目要求只能调整树中节点的指向所以解题方法少了很多，最简单的方法就是在中序遍历的时候修改节点的指向，但是由于每次递归的时候只能修改当前节点的前驱节点，因为这个时候还没有递归到下一个节点所以无法链接下一个节点，虽然在当前节点不能修改下一个节点的后继，但是在递归到下一个节点的时候我们就可以用前驱节点的后继指针指向这个节点，所以我们需要加入一个指针指向每次递归的前一个节点，并且这个节点的传参方式必须是引用传参，只有引用传参才能在每次递归的时候将上一次的指向修改。下面我们直接写代码：
class Solution { public: void _Convert(TreeNode* root,TreeNode*& pre) { if (root==nullptr) { return ; } _Convert(root->left,pre); root->left = pre; if (pre) { pre->right = root; } pre = root; _Convert(root->right,pre); } TreeNode* Convert(TreeNode* pRootOfTree) { if (pRootOfTree==nullptr) { return nullptr; } TreeNode* head = pRootOfTree; while (head->left) { head = head->left; } TreeNode* pre = nullptr; _Convert(pRootOfTree,pre); return head; } };
首先判断根节点是否为空，如果为空则返回空指针。然后我们用一个指针来遍历这个数的左子树直到走到最左边的子树（因为题目要求返回第一个节点，中序遍历的第一个节点是最左子树），然后我们创建一个指针用来记录前驱节点，进入中序遍历函数后，当我们递归完左子树就开始修改链接关系了，先将当前节点的前驱链接上前驱节点（第一次正好将第一个节点的前驱链接置为nullptr）,然后判断前驱节点是否为空，如果不为空我们就可以将前驱节点的后继指针指向当前节点，修改链接关系后让我们的前驱节点变成当前节点，这样下一次递归后才能真正的记录前驱节点。我们画个示意图：
我们仅仅演示了4到6的链接过程，不懂的小伙伴自己画递归图看看。
