1. 根据二叉树创建字符串
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 “()” 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
输入：root = [1,2,3,4] 输出："1(2(4))(3)" 解释：初步转化后得到 "1(2(4)())(3()())" ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。
解题思路
这是一道简单的开胃菜，这个题目可以分为两步来处理：1.如果题目不要求去掉括号，那么其实就是一个简单的前序遍历，将遍历的结果用括号括起来，遇到空树就直接用一个完整的括号代替即可；2.针对括号的去除，可以观察题中给的示例，所谓不必要的括号指的是如果该节点的左右子树都是空，或者左子树不为空，右子树为空，那么就不用补括号，即只有左子树为空右子树不为空才需要额外补充括号；
该题利用字符串直接+=是一个很不错的选择，针对如何将整形数字插入到string对象这个问题可以使用to_string函数来解决：
class Solution { public: string tree2str(TreeNode* root) { if(root==nullptr) return string(" ");//如果是一个空树，直接返回一个空string string str; str+=to_string(root->val);//如果不是空树首先插入根节点的值，再往下 if(root->left) { str+='('; str+=tree2str(root->left); str+=')'; } else if(root->right) { //左子树为空，右子树不为空，需要给左边补一个括号再往右边走 str+="()";//这里要注意是双引号，因为一个完整的括号是一个字符串 } if(root->right) { str+='('; str+=tree2str(root->right); str+=')'; }//右子树为空，不论左子树是否为空都不用加括号 return str; } };
2.二叉树的层序遍历I
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
解题思路
该题大致思想和普通的层序遍历类似，需要借助队列来帮助实现，唯一一点不同就是要求逐层输出，这也是这题的难点，因为一个队列中可能同时存在两层的数据（上述示例中如果9的子树不为空，那么9出队列以后带入第三层值，同时队列中还存在一个第二层的20）；
关于标记节点的层数，这里有两种办法：1.多建一个队列，一个队列用于存放节点的值，另一个队列用于存放该节点的层数，出节点的时候，将两个队列中的值同时出队列； 2.设置一个标志变量，这个标志变量的含义就是某层共有多少个节点，标志变量的大小就是队列中元素个数，因为当我们出完一层后下一层必定全部已经在队列中了；
这里给出第二种解法的代码：
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*>q; vector<vector<int>> vv; if(root) q.push(root); int levelsize=q.size(); while(!q.empty()) { vector<int> level; while(levelsize--) { TreeNode* node=q.front(); q.pop(); level.push_back(node->val); if(node->left) q.push(node->left); if(node->right) q.push(node->right); } vv.push_back(level); levelsize=q.size(); } return vv; } };
3.二叉树的层序遍历II
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
输入：root = [3,9,20,null,null,15,7] 输出：[[15,7],[9,20],[3]]
解题思路
这道题其实很简单，但解题者很可能将这道题想的过于复杂，当我们在读题的时候往往会将自己受限于题目的要求中，比如它要求我们自底向上遍历，我就以为该题的难点就是如果从下往上遍历；但如果不受这句话的限制就会很简单，我们只需要在上一题的基础上将vector逆置即可；
class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { queue<TreeNode*>q; vector<vector<int>> vv; if(root) q.push(root); int levelsize=1; while(!q.empty()) { vector<int> level; while(levelsize--) { TreeNode*node=q.front(); q.pop(); level.push_back(node->val); if(node->left) q.push(node->left); if(node->right) q.push(node->right); } levelsize=q.size(); vv.push_back(level); } reverse(vv.begin(),vv.end()); return vv; } };
4.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
解题思路
该题有两种解法，一种是观察树的结构可以得到这样的一种规律：
class Solution { public: bool IsInTree(TreeNode*root,TreeNode*pos) { if(root==nullptr) return false; return IsInTree(root->left,pos)||IsInTree(root->right,pos)||root==pos; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==nullptr) return nullptr; if(root==p||root==q) return root; bool pInLeft=IsInTree(root->left,p); bool pInRight=!pInLeft;//说了这个节点一定在树中，所以不在左树就一定在右树 bool qInLeft=IsInTree(root->left,q); bool qInRight=!qInLeft; //找到两个节点以后，判断以下两个节点位置 if(qInLeft&&pInRight||qInRight&&pInLeft) return root;//如果节点一左一右，我就是最近祖先 if(pInLeft&&qInLeft)//都在左或者都在右，说明我的左孩子或者右孩子才是最近公共祖先 return lowestCommonAncestor(root->left,p,q); else return lowestCommonAncestor(root->right,p,q); } };
这种解题方法在遇到接近单支的树时效率就会变得很低，因为节点必定都在树的左子树或者右子树中，而我的递归中又嵌套了一个O(N)的递归，所以最差的情况下复杂度为O(N^2)
解题思路二
为了优化针对接近单支二叉树的复杂度情况，这里给出第二种解题思路：设定两个栈用于存放根节点到这两个点的路径节点，将该题转换成类似链表相交的题目，针对入栈时，首先将每个经过的节点都入栈（因为我无法保证该节点是否是路径上的节点），如果某个节点的左右孩子都是空，我们就将该节点出栈（此时可以保证该节点肯定不是我要找的那个节点的路径节点），将两个节点的路径都找完以后，让size大的栈先出栈到两个栈的大小相同，再同时出栈并做判断，第一次出现的相等的值就是最近公共祖先
class Solution { public: bool GetPath(TreeNode*root,TreeNode*x,stack<TreeNode*>&path) { if(root==nullptr) return false; path.push(root);//如果节点不是空，我先插入进去再说 if(root==x) return true; if(GetPath(root->left,x,path))//如果根节点不是，我就去左子树找，左子树找不到就去右子树找 return true; if(GetPath(root->right,x,path)) return true; //走到最后，左子树右子树都为空了，直接将该节点弹出 path.pop(); return false; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { stack<TreeNode*>ppath; stack<TreeNode*>qpath; GetPath(root,p,ppath); GetPath(root,q,qpath); //让长的栈先走 while(ppath.size()!=qpath.size()) { if(ppath.size()>qpath.size()) ppath.pop(); else qpath.pop(); } while(ppath.top()!=qpath.top()) { ppath.pop(); qpath.pop(); } return ppath.top(); } };
这种题目是面试中爱考察的一种，因为更改不同的条件，题目的难易程度也会不同，比如如果该树是一棵搜索二叉树，那么我们第一种解法找节点在哪边的时候就不用写递归，此外如果树是一种三叉链的结构，那么该题就可以转换成链表相交的问题
5.二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
4.你不用输出双向链表，程序会根据你的返回值自动打印输出
示例1
输入：
{10,6,14,4,8,12,16}
返回值：
From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
解题思路
题目要求最后是一个有序的双向链表，而二叉搜索树是基于中序有序的，所以可以知道该题肯定得使用中序遍历，其次要求二叉树的左指针指向前驱节点，右指针指向后继节点（又因为是要求有序的，所以这个操作是在中序遍历中进行的）；该题的注意事项是：为了标记前驱节点，我需要一个指针标记，但是这个在函数中针对这个指针的参数必须要是引用，因为递归中传引用可以使得上一层栈帧中的改变被下一层看到；而且因为第一个节点的左值针要指向空，所以前驱节点指针初始化为空是最好的
class Solution { public: void InOrder(TreeNode*cur,TreeNode*&prev) { if(cur==nullptr) return; InOrder(cur->left,prev); //找到最左节点以后，它的前驱节点要指向空 cur->left=prev; if(prev) prev->right=cur; prev=cur; InOrder(cur->right, prev); } TreeNode* Convert(TreeNode* pRootOfTree) { TreeNode*prev=nullptr; InOrder(pRootOfTree, prev); TreeNode*head=pRootOfTree; while(head&&head->left)//链表最开始的那个节点必定位于树的最左边 { head=head->left; } return head; } };
这里给出递归展开图帮助更好的理解：
补充解法
这题当然不止上面一种解法，我们可以先将这颗树中序遍历的结果存放到一个vector数组中，单独处理第一个节点和最后一个节点（因为第一个节点的左值针要指向空，最后一个节点的右指针要指向空），从第二个结点开始，它的左指针指向前一个元素，右指针指向后一个元素；但是面试中有可能会要求空间复杂度(该题就要求空间复杂度为O(1)）或者禁止使用容器
class Solution { public: void InOrder(TreeNode*cur,vector<TreeNode*>&v) { if(cur==nullptr) return; InOrder(cur->left, v); v.push_back(cur); InOrder(cur->right, v); } TreeNode* Convert(TreeNode* pRootOfTree) { if(pRootOfTree==nullptr) return nullptr;; vector<TreeNode*>v; InOrder(pRootOfTree,v); if(v.size()<=1) return v[0]; v[0]->left=nullptr; v[0]->right=v[1]; for(int i=1;i<v.size()-1;i++) { v[i]->left=v[i-1]; v[i]->right=v[i+1]; } v[v.size()-1]->left=v[v.size()-2]; v[v.size()-1]->right=nullptr; return v[0]; } };
6.从前序与中序序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
解题思路
给定一个前序和中序，或者给定一个中序和后序都是可以构建二叉树的，但是给定一个前序和后序是无法构建二叉树的（因为只能确定根，但无法确定左右子树的节点个数；或者说可以构建二叉树但不唯一）；
有前序和中序序列，我们可以通过前序来确定该树的根，再通过中序来确定根的左右子树区间，所以该题的重点在于标记一个根节点的左右子树区间；大致分为这几步：1.在中序序列中找到这个根的位置 2.获取到起始位置到该位置的前一个位置区间作为左子树区间，获取该位置的下一个位置的区间作为右子树区间，3.递归执行该步骤直到起始位置超过终止位置；因为用到递归，所以函数参数列表中某些变量要给引用
class Solution { public: TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int& previ,int inbegin,int inend) { //递归终止条件：inbegin>inend if(inbegin>inend) return nullptr; //在中序序列中查找根 int rooti=inbegin;//这里不能设等于0，因为递归的时候rooti并不是总是从0位置开始的 while(rooti<=inend) { if(preorder[previ]==inorder[rooti]) break; rooti++; } //找根节点以后要构建根节点作为树的起始 TreeNode*root=new TreeNode(preorder[previ++]);//这里使用一个后置++，因为完成根节点的构建以后要更新根节点 root->left=_buildTree(preorder,inorder,previ,inbegin,rooti-1); root->right=_buildTree(preorder,inorder,previ,rooti+1,inend); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int previ=0; return _buildTree(preorder,inorder,previ,0,inorder.size()-1); } };
如果觉得不好理解可以自行画递归展开图来理解，我感觉我画图太挫了，这里就不继续画了
7.从中序与后序序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出：[3,9,20,null,null,15,7]
解题思路
该题和上一题的解法完全一样，唯一不同的就是后序序列的最后才是根，并且每次更新根的位置使用的是--而不是++，此外因为后序的遍历顺序是左子树右子树根，所以构造完根节点以后要先构造右子树
class Solution { public: TreeNode* _buildTree(vector<int>& inorder,vector<int>& postorder,int& posti,int inbegin,int inend) { //递归终止条件：inbegin>inend if(inbegin>inend) return nullptr; //在中序序列中查找根 int rooti=inbegin;//这里不能设等于0，因为递归的时候rooti并不是总是从0位置开始的 while(rooti<=inend) { if(postorder[posti]==inorder[rooti]) break; rooti++; } //找根节点以后要构建根节点作为树的起始 TreeNode*root=new TreeNode(postorder[posti--]);//这里使用一个后置--，因为完成根节点的构建以后要更新根节点 root->right=_buildTree(inorder,postorder,posti,rooti+1,inend); root->left=_buildTree(inorder,postorder,posti,inbegin,rooti-1); return root; } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { int posti=postorder.size()-1; return _buildTree(inorder,postorder,posti,0,inorder.size()-1); } };
