【C++】二叉树相关算法题

一、根据二叉树创建字符串

题目描述：
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 “()” 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
题目示例：

分析： 根据题意，我们可以观察出一下规律：

1. 根据题意，如果左子树为空，右子树不为空，就需要加空()
2. 如果右子树为空，就不需要加空()
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 str = "";string tree2str(TreeNode* root) {if (root == nullptr)return "";str += to_string(root->val);//根据题意，如果左子树为空，右子树不为空，就需要加空()//如果右子树为空，就不需要加空()//左右子树都为空，就不需要加空()if (root->left || root->right){str += '(';tree2str(root->left);str += ')';}if (root->right){str += '(';tree2str(root->right);str += ')';}return str;}
};

二、二叉树的层序遍历

题目描述：
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
题目示例：

分析：
通过层序遍历二叉树，我们可以通过队列来实现，利用队列先进先出的特点对二叉树进行层序遍历,控制每一层的节点的个数，来实现层序遍历。

/*** 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) {vector<vector<int>> vv;queue<TreeNode*> q;int levelsize = 0;if(root){levelsize = 1;q.push(root);}while(q.size()){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);}levelsize = q.size();vv.push_back(v);}return vv;}
};

三、二叉树的层序遍历 II

题目描述：
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
题目示例：

分析：
思路和上面一样，只需要将上面返回的vector数组逆转就行

/*** 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) {vector<vector<int>> vv;queue<TreeNode*> q;int levelsize = 0;if(root){levelsize = 1;q.push(root);}while(q.size()){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);}levelsize = q.size();vv.push_back(v);}reverse(vv.begin(),vv.end());return vv;}
};

四、二叉树的最近公共祖先

题目描述：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
题目示例：

分析：

1. 第一种思路（时间复杂度O(N^2)）
   我们可以通过观察规律，发现两个节点要不分布在最近祖先的两个不同的子树中，要不分布在最近祖先的同一个子树中（包含祖先），于是我们就可以遍历树中的每一个节点，如果祖先的左右子树中是否有这两个节点或如果祖先本身就是需要查找的节点，就只需要看左子树或右子树是否存在另一个节点，如果有，就证明其是最近的公共祖先。

/*** 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 IsIntree(TreeNode* root,TreeNode* p,TreeNode* q){if(root == nullptr)return false;if(root->val == p->val || root->val == q->val)return true;bool left = IsIntree(root->left,p,q);bool right = IsIntree(root->right,p,q);return left || right;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == nullptr)return nullptr;//p是自己的祖然后在查找q是否在左子树或右子树if(root->val == p->val && (IsIntree(root->left,p,q) || IsIntree(root->right,p,q))){return root;}//q是自己的祖然后在查找p是否在左子树或右子树else if(root->val == q->val && (IsIntree(root->left,p,q) || IsIntree(root->right,p,q))){return root;}//p,q在不在左子树或右子树中的任意一棵树else if(IsIntree(root->left,p,q) && IsIntree(root->right,p,q)){return root;}//这个节点不是最近公共祖先else {TreeNode* Inright = lowestCommonAncestor(root->left,p,q);if(Inright)//不是nullptr就表示这个节点是最近公共祖先return Inright;TreeNode* Inleft = lowestCommonAncestor(root->right,p,q);if(Inleft)//不是nullptr就表示这个节点是最近公共祖先return Inleft;return nullptr;}}
};

3. 第二种思路（时间复杂度O(N)）
   通过前序遍历左子树和右子树，找到对应的节点，并用栈存储从根节点到对应节点的路劲，最后模拟两个链表找交点的情况，长的栈先出栈，直到两个栈的大小相等，在一起出栈，直到两个出栈的节点值相等，就表示其是最近的公共祖先

/*** 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* node,stack<TreeNode*>& Path){if(root == nullptr)return false;Path.push(root);if(root == node)return true;bool left = GetPath(root->left,node,Path);bool right = GetPath(root->right,node,Path);if(!right && !left)Path.pop();return left || right;//左子树和右子树都没有找到}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()){ppath.pop();}while(qpath.size() > ppath.size()){qpath.pop();}while(qpath.top() != ppath.top()){qpath.pop();ppath.pop();}return ppath.top();}
};

五、将二叉搜索树转化为排序的双向链表

题目描述：
将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。
对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
特别地，我们希望可以 就地 完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。
题目示例：

分析：
由题目给出条件，可知该二叉树是二叉搜索树，这题需要我们把二叉搜索树转换为 升序排列 的链表，我们知道二叉搜索树的升序遍历是 中序遍历 ，于是我们就可以定义两个指针 cur 和 prev ，cur 指向当前节点， prev 指向当前节点的上一个节点，通过 中序遍历 树的每一个节点，当当前节点 cur 的左子树遍历完，cur->left = prev ,通过改变前驱和后继的指针的指向，来把其链接已排序的双向循环链表.

/*
// 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 Link(Node* cur,Node*& prev){if(cur == nullptr)return;Link(cur->left,prev);cur->left = prev;if(prev)prev->right = cur;prev = cur;Link(cur->right,prev);}Node* treeToDoublyList(Node* root) {if(root == nullptr)return nullptr;Node* cur = root;Node* prev = nullptr;Link(cur,prev);Node* tail = prev;while(root->left){root = root->left;}Node* head = root;head->left = tail;tail->right = head;return head;}
};

六、从前序与中序遍历序列构造二叉树

题目描述：
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点
题目示例：

分析： 根据前序就可以确定根节点，根据中序就可以确定根节点的左右子树，用区间来表示根节点的左右子树区间，最后就可以确定出整个二叉树。

class Solution {
public://pre_begin,pre_endTreeNode* buildTree_with_pre_in(vector<int>& preorder, vector<int>& inorder,int& pospre,int in_begin,int in_end){if(in_begin > in_end){return nullptr;}//if(pospre <= inorder.size() - 1)TreeNode* newnode = new TreeNode(preorder[pospre++]);int pos;for(int i = in_begin;i <= in_end;i++){if(inorder[i] == newnode->val){pos = i;break;}}if(pospre > inorder.size() - 1)pospre = inorder.size() - 1;TreeNode* left = buildTree_with_pre_in(preorder,inorder,pospre,in_begin,pos - 1);// 左子树if(pospre > inorder.size() - 1)pospre = inorder.size() - 1;TreeNode* right = buildTree_with_pre_in(preorder,inorder,pospre,pos + 1,in_end);// 右子树newnode->left = left;newnode->right = right;return newnode;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i = 0;TreeNode* root = buildTree_with_pre_in(preorder,inorder,i,0,inorder.size() - 1);return root;}
};

七、从中序与后序遍历序列构造二叉树

题目描述：
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历,postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
题目示例：

分析： 与上面的题目类似，只不过是后序遍历，根据后序遍历的特点：左子树-右子树-根节点的特点，我们可以发现把后序反过来，就可以确定根节点的位置，然后再根据中序判断右子树和左子树的位置，其实就是一个 根-右子树-左子树 的过程来创建树，而前序创建树的就是 根-左子树-右子树 ，和前序相比就是遍历子树的顺序变了而已。

/*** 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* buildTree_with_in_post(vector<int>& inorder,vector<int>& postorder,int& pospost,int in_begin,int in_end){if(in_begin > in_end)return nullptr;TreeNode* newnode = new TreeNode(postorder[pospost--]);int pos = -1;for(int i = in_begin;i <= in_end;i++){if(inorder[i] == newnode->val){pos = i;break;}}TreeNode* right = buildTree_with_in_post(inorder,postorder,pospost,pos + 1,in_end);TreeNode* left = buildTree_with_in_post(inorder,postorder,pospost,in_begin,pos - 1);newnode->left = left;newnode->right = right;return newnode;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int i = postorder.size() - 1;//从后序的最后一个节点开始TreeNode* root = buildTree_with_in_post(inorder,postorder,i,0,postorder.size() - 1);return root;}
};

八、非递归实现二叉树的前序遍历

题目描述： 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
题目示例：

分析： 要迭代⾮递归实现⼆叉树前序遍历，⾸先还是要借助递归的类似的思想，只是需要把结点存在栈中，⽅便类似递归回退时取父路径结点。跟这⾥不同的是，这⾥把⼀棵⼆叉树分为两个部分：

1. 先访问左路结点
2. 再访问左路结点的右⼦树
   这⾥访问右⼦树要以循环从栈依次取出这些结点，循环⼦问题的思想访问左路结点的右⼦树。前序遍历的顺序为 根-左子树-右子树 ，我们每次访问一个节点，后需要把它入栈，就可以实现前序遍历。

/*** 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<int> preorderTraversal(TreeNode* root) {vector<int> v;if(root == nullptr)return v;stack<TreeNode*> st;st.push(root);v.emplace_back(root->val);while(root->left){root = root->left;v.emplace_back(root->val);st.push(root);}while(st.size()){TreeNode* cur = st.top();st.pop();cur = cur->right;if(cur){st.push(cur);v.emplace_back(cur->val);}while(cur && cur->left){cur = cur->left;v.emplace_back(cur->val);st.push(cur);}}return v;}
};

九、非递归实现二叉树的中序遍历

题目描述： 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
题目示例：

分析：
中序访问的顺序是 左子树-根-右子树 ，每当访问玩左子树的时候，就将栈顶数据入栈，即可实现中序遍历二叉树

/*** 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<int> inorderTraversal(TreeNode* root) {vector<int> v;if(root == nullptr)return v;stack<TreeNode*> st;st.push(root);while(root->left){root = root->left;st.push(root);}while(st.size()){TreeNode* cur = st.top();v.emplace_back(cur->val); st.pop();cur = cur->right;if(cur){st.push(cur);}while(cur && cur->left){cur = cur->left;st.push(cur);}}return v;}
};

十、非递归实现二叉树的后序遍历

题目描述： 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
题目示例：

分析：:
后序遍历的需要先访问顺序为 左子树-右子树-根 ， 首先我们先把根节点 root 左子树的节点全部加入栈，我们想要访问根，就必须先把根的左子树和右子树都访问完，于是我们就需要用 prev 来表示它当前节点的前一个节点，如果 cur->right == nullptr || cur->right == prev 就表示当前根节点的左子树和右子树都访问完了，然后再出栈，并且不需要向下访问了。

/*** 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<int> postorderTraversal(TreeNode* root) {vector<int> v;if(root == nullptr)return v;stack<TreeNode*> st;st.push(root);TreeNode* prev = nullptr;while(root->left){root = root->left;st.push(root);}while(st.size()){TreeNode* cur = st.top();if(cur->right == nullptr || cur->right == prev){st.pop();v.emplace_back(cur->val);prev = cur;continue;}cur = cur->right;if(cur){st.push(cur);}while(cur && cur->left){cur = cur->left;st.push(cur);}}return v;}
};