根據二叉樹創建字符串
重點是要注意括號省略問題,分為以下情況:
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.按照如此方式就可以完成后序遍歷