＜C++＞ 二叉树进阶OJ题
目录
1. 二叉树创建字符串
2. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
3. 二叉树搜索树转换成排序双向链表
4. 根据一棵树的前序遍历与中序遍历构造二叉树
5. 根据一棵树的中序遍历与后序遍历构造二叉树
6. 二叉树的前序遍历，非递归迭代实现
7. 二叉树中序遍历 ，非递归迭代实现
8. 二叉树的后序遍历 ，非递归迭代实现
1. 二叉树创建字符串
- 此题先遍历左子树，再遍历右子树即可
- 问题在于如何判断在什么时候加括号：如果该节点左边为空，右不为空，则左边括号保留。如果左边为空，右边也为空，那么左右括号都不保留。如果左边不为空，右边为空，则右边括号不保留
- 创建string型变量str，将每一个节点的int 数据to_string为string类型，再由递归层层向下，最终在return之后str全都加起来
class Solution {
public:string tree2str(TreeNode* root) {if (root == nullptr)return "";string 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;}
};2. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
- 如果为三叉链结构（含有父亲节点指针），那么求解公共祖先非常简单，类似求双交链表，将parent指针视为next指针，让底层的节点先走差距步，然后再一个一个的比较，当两个节点相遇时该节点就是公共祖先
- 如果是普通的二叉链式结构， 通过find查找p、q是在左还是在右。因为只要存在一个节点，p、q分别在它的左子树和右子树，那么该节点就是p、q的最近公共祖先！
- 如果root节点是p或q，那么root就是公共祖先（自己可以是自己的祖宗）
class Solution {
public:bool find(TreeNode* r, TreeNode* x){if (r == nullptr)return false;return r == x || find(r->left, x) || find(r->right, x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == nullptr)return nullptr;if (root == p || root == q)return root;bool pInLeft, pInRight, qInLeft, qInRight;pInLeft = find(root->left, p);pInRight = !pInLeft;qInLeft = find(root->left, q);qInRight = !qInLeft;if (pInLeft && qInLeft){return lowestCommonAncestor(root->left, p, q);}else if (pInRight && qInRight){return lowestCommonAncestor(root->right, p, q);}else{return root;}}
};该算法时间复杂度是什么？
O（N*N），猜测该树状结构为最坏情况，全都在一条分支，每一次都find，最坏在高度次找到
如何优化到 O(N) ？
使用前序遍历，用stack来记录到达p、q路径上的节点（比较相等时，比较指针，因为树内可能有相等的值），最后转化为类似相交链表的问题
左右都找不到，那么就pop掉该节点的，因为该节点不在p、q的路径上
//方法二：前序遍历获取p、q路径，用stack记录路径上节点，最后转化为相交链表问题bool FindPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path){if (root == nullptr)return false;path.push(root);if (root == x)return true;if (FindPath(root->left, x, path))return true;if (FindPath(root->right, x, path))return true;//左右都找不到，就会到这里，那么就pop掉该节点的，因为该节点不在p、q的路径上path.pop();return false; }TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> pPath, qPath;FindPath(root, p, pPath);FindPath(root, q, qPath);while (pPath.size() > qPath.size()){pPath.pop();}while (pPath.size() < qPath.size()){qPath.pop();}while (pPath.top() != qPath.top()){pPath.pop();qPath.pop();}return qPath.top();}3. 二叉树搜索树转换成排序双向链表
在诸多要求下，该如何链接？
创建两个指针，prev、cur，然后采用中序遍历（中序遍历的顺序就是双链表的顺序），cur先走，prev在后，到达一个节点时，它的上一个节点 prev 的 right 链接 cur，cur 的 left 链接 prev，然后更新prev，继续递归
在中序遍历时，要注意参数prev的类型，是TreeNode*的引用！这是为了在树最底层的栈帧中prev被更新返回上一个函数栈帧后，prev也是新的，可以被使用
链接完成后，找到左子树最左节点，该节点就是head，返回该节点就是答案
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，注意参数要用&，因为所有递归函数要用统一的prev，prev更新之后可以立即使用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;}
};4. 根据一棵树的前序遍历与中序遍历构造二叉树
前序序列（根 左子树 右子树）：用来确定根
- 中序序列（左子树 根 右子树）：根据根来分割左右区间，当区间不存在时分割完成
- 让控制先序遍历数组的下标 prei 一直往后走，再在中序遍历的数组中找到对应的值，根据这个值的下标分割数组，将子区间各自递归下去
class Solution {
public: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]);//在中序数组内找，prei对应的根int rooti = inbegin;while (rooti <= inend){if (inorder[rooti] == preorder[prei])break;++rooti;}//往后走，分割区间继续递归++prei;//链接是从低到顶链接的，即递归到最底往上的时候开始链接//[inbegin, rooti - 1] rooti [rooti + 1, inend]root->left = _buildTree(preorder, inorder, prei, inbegin, rooti - 1);root->right = _buildTree(preorder, inorder, prei, rooti + 1, inend);;return root;} TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i = 0;TreeNode* root = _buildTree(preorder, inorder, i, 0, inorder.size() - 1);return root;}
};
5. 根据一棵树的中序遍历与后序遍历构造二叉树
- 同理，有中序和后序，由于后序（左子树 右子树 根）的特性，控制下标从后往前走，并先构建右子树
class Solution {
public:TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& posti, int inbegin, int inend) {if (inbegin > inend)return nullptr;TreeNode* root = new TreeNode(postorder[posti]);int rooti = inbegin;while (rooti <= inend){if (inorder[rooti] == postorder[posti])break;++rooti;}--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 i = postorder.size() - 1;TreeNode* root = _buildTree(inorder, postorder, i, 0, inorder.size() - 1);return root;}
};
6. 二叉树的前序遍历，非递归迭代实现 
- 访问一棵树，分为两部分：左路节点，左路节点的右子树，这一点很重要，有递归思想，是解题关键
- 用栈来实现前序遍历，将左路节点的指针入栈，将访问的值存入vector
- 开始访问右子树时先将栈顶元素出栈，以子问题的方式访问右子树，循环起来
依托于栈的特性，后进先出，使得访问顺序就是前序
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root;vector<int> v;while (cur || !st.empty()){//访问一颗树的开始//访问左路节点，将所有root的所有左路节点入栈，后序在访问左路节点的右子树while (cur){v.push_back(cur->val);st.push(cur);cur = cur->left;}//依次访问左路节点的右子树TreeNode* top = st.top();st.pop();//以子问题的方式访问右子树cur = top->right;}return v;}
};7. 二叉树中序遍历 ，非递归迭代实现
- 很简单，将v的push_back放在出栈时就可以打到中序遍历的效果
- 从栈里面pop一个节点，意味着这个节点的左子树已经访问完了
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root;vector<int> v;while (cur || !st.empty()){//访问一颗树的开始//访问左路节点，将所有root的所有左路节点入栈，后序在访问左路节点的右子树while (cur){st.push(cur);cur = cur->left;}//依次访问左路节点的右子树TreeNode* top = st.top();st.pop();v.push_back(top->val);//以子问题的方式访问右子树cur = top->right;}return v;}
};8. 二叉树的后序遍历 ，非递归迭代实现
- 按照后序遍历，如果一个节点的右子树没有访问过（正准备访问），那么它的上一个访问节点是左子树的根；如果让的右子树已经访问过了（刚刚访问完），那么它的上一个访问节点是右子树的根
- 所以后序遍历的访问时机就是，如果该节点访问到第二次了，那么这个节点的val就要被push_back进vector中了，或者如果该节点没有右子树，那么这个节点的val也要被push_back进vector中
- 所以如何判断该节点已经访问过两次了？答案就是用prev记录上一个已经访问的节点！
- 一个节点的右子树为空或者上一个访问的节点是右子树的根，都说明该节点的右子树已经访问完了，可以访问当前节点了！
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* prev = nullptr;TreeNode* cur = root;while (cur || !st.empty()){//访问一颗树的开始//访问左路节点，将所有root的所有左路节点入栈，后序在访问左路节点的右子树while (cur){st.push(cur);cur = cur->left;}TreeNode* top = st.top();//一个节点的右子树为空或者上一个访问的节点是右子树的根//都说明该节点的右子树已经访问完了，可以访问当前节点了！if (top->right == nullptr || top->right == prev){prev = top;v.push_back(top->val);st.pop();}else cur = top->right;}return v;}
};