数据结构二叉树进阶

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

1.题目

2. 分析原理

要把二叉树元素按照前序顺序取出来，并且以字符串的形式返回，还要添加括号对于左子树和右子树，那么第一步就是向定义一个string类型来接收取出的元素，需要用到to_string函数把整型变成string类型，第二步就是递归来深度遍历了，但是需要判断一下，题目有些情况是省略了括号，有些没有省去，题目例子可以知道左为空右不为空就不能省略括号，左不为空右为空就可以省略括号，所以遍历左子树就要left||right，这样包含了对左为空右不为空的情况，遍历右子树深度时只需要判断root->right存不存在就行，不在就之间省略括号。

3.代码实现

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:string tree2str(TreeNode* root) {string string;if(root==NULL)return string;string+=to_string(root->val);if(root->left||root->right){string+='(';string+=tree2str(root->left);string+=')';}if(root->right){string+='(';string+=tree2str(root->right);string+=')';}return string;}
};

2.二叉树的层序遍历

1.题目

2.分析原理

题目要求的是把每一层的结点都放在同一个[]里，需要知道那些结点是同一层且第几层，就定义一个levelSize来计数，计算每层存在多少个结点，然后循环放到vector里面，循环次数就是levelSize，循环结束后就把vector的数据放到vector<vector>里面，也就是说levelSize的循环结束就代表一层数据已经取出，还需要再套一层循环在外面，因为要一直更新levelSize的值并一直取结点，直到levelSize的值为0，代表此层没有结点，也就是叶子的下一层了。

3.代码实现

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {int levelSize=0;queue<TreeNode*> q;vector<vector<int>> vv;if(root){q.push(root);levelSize=1;}while(levelSize>0){vector<int> v;while(levelSize--){TreeNode* front=q.front();q.pop();v.push_back(front->val);if(front->left)q.push(front->left);if(front->right)q.push(front->right);}vv.push_back(v);levelSize=q.size();}return vv;}
};

题目二

代码实现

只需要加个逆置函数，把vv逆置就可以

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {int levelSize=0;queue<TreeNode*> q;vector<vector<int>> vv;if(root){q.push(root);levelSize=1;}while(levelSize>0){vector<int> v;while(levelSize--){TreeNode* front=q.front();q.pop();v.push_back(front->val);if(front->left)q.push(front->left);if(front->right)q.push(front->right);}vv.push_back(v);levelSize=q.size();}reverse(vv.begin(),vv.end());return vv;}
};

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

1.题目

2.分析原理

要找到公共祖先，那么俩个结点一定是子孙，也就是会在公共祖先的左右结点处，也可能是在一边，根据例子看，还有特殊情况，就是其中一个结点是祖先。开始前就可以判断是否有结点是祖先，然后构建函数判断是否在左边，而右边函数就可以不用写了，因为不是左就是右，得到两结点的方位值(true为左，false为右)，就可以用来走判断了，如果是一左一右那么就返回这个结点，反着也是，接下来是同左边，就要递归了，因为要用一左一右和其中一个为祖先来找，同右也是，只是用来移动位置来触发一左一右和有一个为祖先的情况。

3.代码实现

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool Inleft(TreeNode* root,TreeNode* x){if(root==nullptr)return false;return root==x||Inleft(root->left,x)||Inleft(root->right,x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==p||root==q)return root;bool pIsleft=Inleft(root->left,p);bool pIsright=!pIsleft;bool qIsleft=Inleft(root->left,q);bool qIsright=!qIsleft;if(pIsleft&&qIsright||pIsright&&qIsleft)return root;else if(pIsleft&&qIsleft){return lowestCommonAncestor(root->left,p,q);}else if(pIsright&&qIsright){return lowestCommonAncestor(root->right,p,q);}return nullptr;}
};

优化

前一个方法的时间复杂度是高的，如果是极端情况”单马尾“就会一直递归，判断方位要递归，移动位置也要递归，那么方位要n次，移动位置也要n次，一共就是O(N^2)了。优化策略就是求出俩个结点到根的路径，就可以转换为两个数组找到相同值交点问题。

如下图，p为6结点，按照前序访问，先把3入栈并判断左右是否有目标结点，有就可以保留，然后是入5并判断，到6就是目标结点保留并返回，而2 7 4是找到目标结点返回就不入栈了。

q为4结点，先入35，然后6入，但是因为没有目标结点在6的左右子数就踢出去，到2，到7，而7也是跟6一样踢出去，就到4了找到并返回。

这样就得到两个路径了，通过找交点就可以找到祖先是哪一个了。

代码实现

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool GetPath(TreeNode* root,TreeNode* x,stack<TreeNode*>& s){if(root==nullptr)return false;s.push(root);if(root==x)return true;if(GetPath(root->left,x,s))return true;if(GetPath(root->right,x,s))return true;s.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> pPath,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();}
};

4.将二叉树搜索树转换为排序的双向链表

1.题目

2.分析原理

因为要最小元素，就可以用中序遍历，得到有序的数组，返回最前面，遍历过程修改左指针为前驱和右指针为后继指针。定义cur和prev，cur为当前中序遍历到的结点，prev为上一个中序遍历的结点，cur->left,cur->left指向prev，cur->right无法指向中序的下一个，但是可以prev->right指向cur;

个人：总的来说就是双指针思路，一前一后，前后相连，双指针路线就是中序遍历的路线，边走边修改连接方式，最后用循环找到最左结点，并头尾相连完成双链表，返回head。

3.代码实现

/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node() {}Node(int _val) {val = _val;left = NULL;right = NULL;}Node(int _val, Node* _left, Node* _right) {val = _val;left = _left;right = _right;}
};
*/
class Solution {
public:void InOrderR(Node* cur,Node* &prev)//要用引用，因为指针本身也是变量，所以会把存储变量传过去，形参是不会指向地址指向的内容的{if(cur==nullptr)return ;//下面是左子树部分InOrderR(cur->left,prev);cur->left=prev;if(prev)prev->right=cur;prev=cur;//更新位置//上面就是根节点部分操作//下面是右子树部分InOrderR(cur->right,prev);}Node* treeToDoublyList(Node* root) {if(root==nullptr)return nullptr;Node* prev=nullptr;InOrderR(root,prev);Node* head=root;//这个根节点是二叉树状态时的根，要用循环找到链表的最左边while(head->left){head=head->left;}head->left=prev;prev->right=head;return head;}
};

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

1.题目

2.分析原理

给出前序遍历的数组和中序遍历的数组来构建二叉树，前序数组可以给出头节点的位置，而中序数组可以根据前序所确定的头节点来分割左右子树的区间，然后用递归来连接结点。首先定义一个变量来作为下标遍历前序数组，这个变量传参要用引用，因为这个值需要记录，在root->left结束后，此时prei就不会找到左子树的根了，因为已经记录完了，剩下就是右子树的根了。还需要begin和end来作为区间表示，用来分割完后把区间传参，在小区间里再次找到根节点，然后又分割区间，直到都返回nullptr为止。

注意：root->left走完后，inbegin和inend已经被改了，不是0了。

3.代码实现

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* Tree(vector<int>& preorder, vector<int>& inorder,int& prei,int inbegin,int inend){if(inbegin>inend)return nullptr;TreeNode* root=new TreeNode(preorder[prei]);int rooti=inbegin;while(rooti<inend){if(preorder[prei]==inorder[rooti]){break;}elserooti++;}prei++;root->left=Tree(preorder,inorder,prei,inbegin,rooti-1);//把左子树的根找完剩下就是右子树根，prei是要++才能实现用完找完root->right=Tree(preorder,inorder,prei,rooti+1,inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i=0;return Tree(preorder,inorder,i,0,preorder.size()-1);}
};