【C++】二叉樹相關算法題

一、根據二叉樹創建字符串

題目描述：
給你二叉樹的根節點 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: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 的深度盡可能大（一個節點也可以是它自己的祖先）。
題目示例：

分析：

第一種思路（時間復雜度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;}}
};

第二種思路（時間復雜度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 ，返回它節點值的前序遍歷。
題目示例：

分析： 要迭代?遞歸實現?叉樹前序遍歷，?先還是要借助遞歸的類似的思想，只是需要把結點存在棧中，?便類似遞歸回退時取父路徑結點。跟這?不同的是，這?把?棵?叉樹分為兩個部分：

先訪問左路結點
再訪問左路結點的右?樹
這?訪問右?樹要以循環從棧依次取出這些結點，循環?問題的思想訪問左路結點的右?樹。前序遍歷的順序為 根-左子樹-右子樹 ，我們每次訪問一個節點，后需要把它入棧，就可以實現前序遍歷。

/*** 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;}
};