相关二叉树进阶面试题的讲解？看这一篇足矣

引子：我们在之前学过c语言的二叉树，但是c++来做更好！本期要讲的题目如下(其实有点拖欠了，很久之前，就想写这个了，今天终于克服自己的欲望，达成了这个愿望）

1， 二叉树创建字符串

思路：基于前序遍历，考虑括号的是否可删除情况！如果左为空，但是右不为空，则不能删除，否则不能确定原先顺序！其他括号直接删掉

代码：

class Solution {
public:string tree2str(TreeNode* root) {string answer;if(root==nullptr)return answer;answer+=to_string(root->val);if(root->left!=nullptr ||root->right){answer+='(';answer+=tree2str(root->left);answer+=")";}//if(root->right)if(root->right!=nullptr){answer+='(';answer+=tree2str(root->right);answer+=")";}return answer;}
};

2， 二叉树的分层遍历1

思路：借助每一次插入数组size就是每一层的元素个数，每一层数据存储在一个一维顺序表中，

然后利用queue队列来进行临时工具过度

代码：

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> answer;if (root == nullptr) {return answer;}size_t size = 0;queue<TreeNode*> h;if (root) {h.push(root);size = 1;}while (size) {vector<int> c;while (size--) {TreeNode* front = h.front();h.pop();c.push_back(front->val);if (front->left) {h.push(front->left);}if (front->right) {h.push(front->right);}}size = h.size();answer.push_back(c);}return answer;}
};

3， 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

思路：观察特征，发现最近的公共祖先是p,q在二侧，直接进行判断就行

或利用二条路径的相交点就是最近的公共祖先

代码：

class Solution {
public:bool is_intree(TreeNode* root, TreeNode* x) {if (root == nullptr) {return false;}return root == x || is_intree(root->left, x) ||is_intree(root->right, x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == nullptr) {return nullptr;}if (root == q || root == p) {return root;}bool qleft = is_intree(root->left, q);bool qright = !qleft;bool pleft = is_intree(root->left, p);bool pright = !pleft;if (qleft && pright || qright && pleft) {return root;} else if (qleft && pleft) {return lowestCommonAncestor(root->left, p, q);} else {return lowestCommonAncestor(root->right, p, q);}}
};

4， 二叉树搜索树转换成排序双向链表

思路：进行遍历的同时修改指向，可以有一个前驱节点，提前知道自己的未来是什么，或知道后面指向那里，再进行left等赋予节点

代码：

class Solution {public:// TreeNode* Left(TreeNode*t)// {//  while(t->left)//  {//      t=t->left;//  }//  return t;// }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*head=Left(pRootOfTree);if (pRootOfTree == nullptr) {return nullptr;}TreeNode* prev = nullptr;INOrder(pRootOfTree, prev);TreeNode*head=pRootOfTree;while(head->left){head=head->left;}while(prev!=head){prev=prev->left;}// prev->right=head;// head->left=prev;return prev;}
};

5. 根据一棵树的前序遍历与中序遍历构造二叉树

思路：前序：根左右，中序：左根右；在inoreder里面找根节点，以根节点位置以左是左子树，以右为右子树！递归实现

代码：

class Solution {
public:TreeNode* answer(vector<int>& preorder, vector<int>& inorder, int& t,int lefti, int righti) {if (lefti>righti) {return nullptr;}TreeNode* root = new TreeNode(preorder[t]);int v = lefti;while (v <= righti) {if (inorder[v] == preorder[t]) {break;} else {v++;}}t++;root->left = answer(preorder, inorder, t, lefti, v - 1);root->right = answer(preorder, inorder, t, v + 1, righti);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i = 0;return answer(preorder, inorder, i, 0, inorder.size() - 1);}
};

6. 二叉树的前序遍历，非递归迭代实现

思路：利用栈的特点，先遍历左节点，在找左节点的右子树或右节点，栈为空或cur=nullptr为结束条件

代码：

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> h;vector<int> answer;TreeNode*cur=root;while(cur || !h.empty()){while(cur){h.push(cur);answer.push_back(cur->val);cur=cur->left;}TreeNode* top=h.top();h.pop();cur=top->right; }return answer;}
};

希望帮到大家，其他的题知识大同小异！