【C++】二叉樹進階面試題

根據二叉樹創建字符串

重點是要注意括號省略問題，分為以下情況：
1.左字樹為空，右子樹不為空，左邊括號保留
2.左右子樹都為空，括號都不保留
3。左子樹不為空，右子樹為空，右邊括號不保留

如果根節點為空，返回空字符串。創建一個字符串將根節點的值轉換為字符串并存儲在 str 中，將整數值轉化為字符串目的可以直接進行追加操作。
代碼邏輯：
1.本質上是一個前序遍歷，在遍歷前加‘(‘遍歷后加’)’
2.左子樹加括號的條件用if(root->left||root->right)就完美描述，左子樹為空判斷第二個條件，右子樹也不為空就+（），若第一條件左子樹不為空直接成立也+（）。調用左子樹遞歸來追加key值到字符串中
2.只要右子樹不為空就加（），調用右子樹遞歸來追加key值到字符串中

二叉樹的最近公共祖先

若直接是一棵搜索二叉樹，能確定pq大小，在左子樹還是右子樹。
一般情況下普通樹情況居多，思路：
1.一個在左邊，一個在右邊，當前根就是公共祖先
2.p或q就是根，另外一個在其子樹中，當前根就是公共祖先

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/bool find(TreeNode* root,TreeNode* x){if(root==nullptr){return false;}return root==x||find(root->left,x)||find(root->right,x);}
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==nullptr)return nullptr;//處理根節點就是pq情況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;//處理pq都在左邊情況if(pinleft&&qinleft){return lowestCommonAncestor(root->left, p, q);}//處理都在右邊情況else if(pinright&&qinright){return lowestCommonAncestor(root->right, p, q);}//處理一左一右情況else{return root;}}
};

代碼邏輯：
1.創建一個find函數去查找pq值所在節點，當前根不是就按前序遞歸查找
2.創建pinleft等狀態值，通過調用find函數來確定pq的存在情況
3.處理pq都在左子樹和右子樹情況，分別調用遞歸，成功返回root節點
4.最后pq一左一右情況直接返回根節點
精髓在于，通過遞歸從整個二叉樹逐步縮小樹的范圍，pq最終會呈現出一左一右的情況。

時間復雜度分析：
find 函數最壞情況下，可能需要訪問子樹中的所有節點，需要遍歷 O(n) 個節點。lowestCommonAncestor 函數最壞情況下，如樹是完全不平衡的（退化為鏈式結構），此時遞歸調用的次數為 O(n)，所以總的時間復雜度為 O(n2)。

倒著走，轉化為鏈表相交類似問題

 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掉該路節點，換路尋找path.pop();return false;}
class Solution {
public: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(qpath.size()>ppath.size()){qpath.pop();}//一起走，尋找相交節點while(ppath.top()!=qpath.top()){ppath.pop();qpath.pop();}return ppath.top();}
};

FindPath查找路徑函數，利用棧后進先出的特性來實現。
1.空節點返回失敗，不為空先入棧，在判斷是否為目標值
2.當前節點為目標值返回成功，否則通過if條件套用去遞歸按照前序遍歷尋找
3.若沒找到，要pop節點，告訴父節點該方向沒有，換一個方向
lowestCommonAncestor 函數
1.pq分別創建一個棧，通過路徑查找函數招到各自路徑
2.相交鏈表處理思路，長的先走差距步，再一起走，第一次相遇點即為相交點。
3.長的先走，只要長度長于短的通過循環pop掉，最后一起走只要不相等就pop掉，最后隨便返回一個棧頂元素，有可能為空。

二叉樹搜索樹轉換成排序雙向鏈表

在這里插入圖片描述

思路：
因要轉化成一個排序的雙向鏈表，所以要用到中序遍歷，至于如何轉化成雙向鏈表，需將中序遍歷部分添加前后指針
1.前指針開始置空，鏈接完后更新為當前節點，當前節點往下遞歸，再鏈接，如此下去直到結束
2.后指針如何鏈接？我們無法預知未來，若是穿越者就可，所以當遍歷到下一個節點時，將上一個節點(需判斷不為空時)的后指針指向當前節點，就完成了后指針鏈接的難題，中序遍歷最后節點的后指針一定為空。
注意：
InOrder函數傳參時prev要傳指針的引用，因為再遞歸過程中會不斷開辟新的棧幀，不傳引用沒辦法控制每個棧幀中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) {}* };*/TreeNode* build(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=prei;prei每次遞歸都會增加，所以在遞歸過程中可能讓rooti錯失根節點//位置，導致劃分區間出現問題，會導致數組越界問題int rooti=inbegin;while(rooti<inend){if(preorder[prei]==inorder[rooti])break;rooti++;}//劃分好區間[inbegin,rooti-1]rooti[rooti+1,inend]//按前序遍歷依次遞歸，鏈接節點prei++;root->left=build(preorder,inorder,prei,inbegin,rooti-1);root->right=build(preorder,inorder,prei,rooti+1,inend);return root;}
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i=0;TreeNode*root=build(preorder,inorder,i,0,inorder.size()-1);return root;}
};

1.結束條件：創建節點函數中當初下標大于尾下標時無法構建出區間，返回空節點
2.用前序vector和其下標prei來創建節點，第一次為根節點，后面prei不斷更新依次創建出前序遍歷中每個節點
3.通過循環比較來找出中序vector中根節點位置，從而劃分區間
4.通過遞歸調用按照前序遍歷依次鏈接每個節點，返回根節點。每進行一次遞歸，prei都要++，直到遍歷完前序vector，為確保每次遞歸新創建的棧幀中prei相同，參數要傳引用。

二叉樹的前序遍歷，非遞歸迭代實現

思路：

前序遍歷，最先訪問到的節點是左路節點，再訪問左路節點的右子樹。我們可以利用棧后進先出的特性來實現
1.創建一個vector來實現最終輸出，一個stack來實現遍歷操作，一個cur代替根節點進行遍歷
2.循環條件，當前節點cur和棧其中一個不為空。cur是訪問一棵樹的開始，先訪問左路節點，依次如棧，節點值也依次如vector
3.依次訪問左路節點的右子樹，創建top取棧頂元素，再pop掉，因為已經訪問過了，棧中剩余元素是未訪問的。利用子問題的方式訪問右子樹，將cur更新為右子樹，進行循環遍歷。

/*** 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;stack<TreeNode*>st;TreeNode*cur=root;while(cur||!st.empty()){//訪問的開始，先訪問左子樹while(cur){v.push_back(cur->val);st.push(cur);cur=cur->left;}//訪問左子樹的右子樹TreeNode*top=st.top();st.pop();//訪問右子樹轉化為子問題cur=top->right;}return v;}
};

總結：

通過棧后進先出特性能確保從下往上依次訪問左子樹的右樹，滿足前序性質。本質還是遞歸的思想，不過用循環來實現。依次訪問左節點的右子樹，還是會將其轉化為先訪問左子樹，再訪問左子樹的右子樹的子問題

二叉樹中序遍歷，非遞歸迭代實現

與前序遍歷的非遞歸思路相同，只是左路節點的訪問時機不同
思路：
1.左路節點入棧 2.訪問左路節點及左路節點右子樹
本質：在遍歷左節點過程中先不入vector，從棧中取到一個節點，意味著這個節點的左子樹已經訪問完了，再把當前節點入vector

因為先遍歷左節點，最后肯定遇到空結束，代表最后節點左子樹為空，已經訪問完了，再取棧頂元素，然后pop掉，意味著當前節點的左子樹已訪問完，當前節點作為根節點入vector，再將當前節點更新為其右子樹，滿足了中序遍歷性質。再取棧頂元素，舊棧頂元素(上一次pop掉的)作為當前棧頂元素的左子樹已被訪問過并且已經入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<int> inorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*>st;TreeNode*cur=root;while(cur||!st.empty()){//訪問的開始，先訪問左子樹while(cur){st.push(cur);cur=cur->left;}//訪問左子樹的右子樹TreeNode*top=st.top();st.pop();v.push_back(top->val);//訪問右子樹轉化為子問題cur=top->right;}return v;}
};

可看出與前序遍歷的非遞歸實現，僅僅是v.push_back(top->val);的執行順序不同，中序遍歷放在了取棧頂元素之后，而前序遍歷放在了遍歷左節點時直接訪問

二叉樹的后序遍歷，非遞歸迭代實現

按照左子樹右子樹根的順序訪問，如何在訪問根節點前訪問右子樹呢？

采取比較的方式，容易理解和操作：
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:vector<int> postorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*>st;TreeNode*prev=nullptr;TreeNode*cur=root;while(cur||!st.empty()){//訪問的開始，先遍歷左子樹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;}
};

需要創建一個prev來保存上一個訪問過的節點，通過一個圖來分析感受一下

1.先遍歷左節點，124依次入棧
2.取棧頂元素4，其左子樹為空相當于訪問過了，其右子樹為空也相當于訪問過了，直接將4入vector，將prev更新為當前top，然后pop
3.繼續取棧頂元素2，其左子樹4已訪問過，其右樹不為空，更新當前結點為其右樹，返回循環，劃分為子問題，56依次入棧，取棧頂元素6，其左子樹和右子樹為空相當于訪問過，直接將6入vector，然后pop。繼續取棧頂元素5，其左子樹6已訪問過，右子樹不為空，更新當前節點為其右子樹，如此循環。剩下部分分析省略，思路相同
4.按照如此方式就可以完成后序遍歷