前中后序的遞歸實(shí)現(xiàn)
void ff(TreeNode* p,vector<int> &v){
if(p==nullptr)
return;
v.push_back(p->val);
ff(p->left,v);
ff(p->right,v);
}
void mf(TreeNode* p,vector<int> &v){
if(p==nullptr)
return;
mf(p->left,v);
v.push_back(p->val);
mf(p->right,v);
}
void bf(TreeNode* p,vector<int> &v){
if(p==nullptr)
return;
bf(p->left,v);
bf(p->right,v);
v.push_back(p->val);
}
前中后序的非遞歸標(biāo)準(zhǔn)實(shí)現(xiàn)
void ff(TreeNode* root,vector<int>& v){
TreeNode* p=root;
stack<TreeNode*> s;
while(!s.empty() || p){
while(p){
v.push_back(p->val);//Visit
s.push(p);
p=p->left;
}
p=s.top();
s.pop();
p=p->right;
}
}
void mf(TreeNode* root,vector<int>& v){
TreeNode* p=root;
stack<TreeNode*> s;
while(!s.empty() || p){
while(p){
s.push(p);
p=p->left;
}
p=s.top();
v.push_back(p->val);//Visit
s.pop();
p=p->right;
}
}
void bf(TreeNode* root,vector<int>& v){
TreeNode* p=root,*plast=nullptr;
stack<TreeNode*> s;
while(!s.empty() || p){
while(p){
s.push(p);
p=p->left;
}
p=s.top();
if(!p->right || plast==p->right){
v.push_back(p->val);//Visit
s.pop();
plast=p;
p=nullptr;//既然沒有右子樹或者右子樹已經(jīng)被訪問，那么p就沒有用了，應(yīng)該讓它失效，這樣才會從棧頂，彈出根節(jié)點(diǎn)
}else
p=p->right;
}
}
總結(jié)
整體的思路是這樣的：
- 指針p指向root，創(chuàng)建棧
- 當(dāng)棧不為空或p有效時(shí)，循環(huán)：
- 沿著根節(jié)點(diǎn)的左分支一路壓入根節(jié)點(diǎn)（如果是前序遍歷此時(shí)就可以訪問p）
- 循環(huán)結(jié)束時(shí)p為空，此時(shí)p失效。
- 當(dāng)p失效時(shí)，從棧頂彈出結(jié)點(diǎn)（如果是中序遍歷此時(shí)就可以訪問p）。此時(shí)彈出的一定是底層的結(jié)點(diǎn)。
- 對該結(jié)點(diǎn)進(jìn)行訪問，并嘗試訪問其右分支。
- 右分支的結(jié)點(diǎn)視作根節(jié)點(diǎn)，重復(fù)以上過程。
當(dāng)后序遍歷時(shí)，預(yù)先設(shè)置plast為空，以記錄上一次訪問的結(jié)點(diǎn)。
取棧頂元素作p，
- 當(dāng)p無右分支或p的右分支已被訪問時(shí)
- 訪問p
- 彈出棧頂
- 更新plast
- 設(shè)置p失效（p失效之后才會從棧頂彈元素）
- 否則（當(dāng)p有右分支且右分支沒有被訪問）
p=p->right 右分支作根節(jié)點(diǎn)進(jìn)入循環(huán)進(jìn)行訪問
簡單來說，p相當(dāng)于當(dāng)前操作的子樹；當(dāng)p失效時(shí)，彈出棧頂元素，即使當(dāng)前操作的子樹的根。左邊處理完了，就索引根，通過根來索引右子樹。
層遍歷與前序遍歷的非標(biāo)準(zhǔn)實(shí)現(xiàn)
前序遍歷的非標(biāo)準(zhǔn)實(shí)現(xiàn)
流程：
- 判斷root是否為空
- 指針p指向root
- 創(chuàng)建棧并壓入p
- 當(dāng)棧不為空時(shí)：循環(huán)
- 彈出棧頂元素進(jìn)行訪問
- 如果該元素有右分支，壓入右孩子
- 如果該元素有左分支，壓入左孩子
void ff2(TreeNode* root,vector<int>& v){
if(!root)
return;
TreeNode* p=root;
stack<TreeNode*> s;
s.push(p);
while(!s.empty()){
p=s.top();
s.pop();
v.push_back(p->val);
if(p->right)
s.push(p->right);
if(p->left)
s.push(p->left);
}
}
層遍歷
流程：
- 判斷root是否為空
- 指針p指向root
- 創(chuàng)建隊(duì)列并壓入p
- 當(dāng)隊(duì)列不為空時(shí)：循環(huán)
- 彈出隊(duì)首元素進(jìn)行訪問
- 如果該元素有左分支，壓入左孩子
- 如果該元素有右分支，壓入右孩子
void layer(TreeNode* root,vector<int> &v){
if(!root)
return;
TreeNode* p=root;
queue<TreeNode*> q;
q.push(p);
while(!q.empty()){
p=q.front();
v.push_back(p->val);
q.pop();
if(p->left)
q.push(p->left);
if(p->right)
q.push(p->right);
}
}
擴(kuò)展：層打印
按層打印到一個(gè)二維數(shù)組中。
該問題的難點(diǎn)在于如何判斷當(dāng)前訪問的結(jié)點(diǎn)是不是某一行的行末。所以我們使用nlast指針，來記錄當(dāng)前行的行末；用last指針來記錄最近壓入隊(duì)列的結(jié)點(diǎn)。
- 初始時(shí)last和nlast都為root
- 循環(huán)時(shí)，last記錄最近壓入的結(jié)點(diǎn)
- 當(dāng)前訪問的結(jié)點(diǎn)等于nlast時(shí)，表示已經(jīng)訪問到了某一行的行末。這個(gè)時(shí)候做行末相關(guān)的處理，并將nlast更新為last。因?yàn)楫?dāng)某一行訪問完成后，新壓入的結(jié)點(diǎn)，一定是下一行的行尾。
void layer(TreeNode* root,vector<vector<int> > &v){
if(!root)
return;
TreeNode* p=root;
queue<TreeNode*> q;
q.push(p);
TreeNode* last=root,*nlast=root; //last和nlast初始化為root
vector<int> temp;
while(!q.empty()){
p=q.front();
q.pop();
temp.push_back(p->val);
if(p->left){
q.push(p->left);
last=p->left; //記錄last
}
if(p->right){
q.push(p->right);
last=p->right;//記錄last
}
if(p==nlast){//如果p指針已經(jīng)到達(dá)了一行的行末，那么最新壓入棧的last一定是下一行的行末
v.push_back(temp);
temp.clear();
nlast=last;
}
}
}
擴(kuò)展：判滿、完全二叉樹
判斷完全二叉樹
思路：按層遍歷二叉樹，直到發(fā)現(xiàn)第一個(gè)非滿結(jié)點(diǎn)（單左或葉子結(jié)點(diǎn)，不可以是單右）。在這個(gè)結(jié)點(diǎn)之后，所有的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)。那么該樹就是完全二叉樹。
bool chk(TreeNode* root) {
//按層遍歷，找到第一個(gè)不滿結(jié)點(diǎn)，其后所有結(jié)點(diǎn)必須是葉子
if(!root)
return false;
TreeNode *p=root;
queue<TreeNode*> que;
que.push(p);
int find=0;
while(!que.empty()){
p=que.front();
que.pop();
if(p->left){
que.push(p->left);
}
if(p->right){
que.push(p->right);
}
if(!p->right){//沒有右樹，就涵蓋了葉子和單左 兩種情況
find=1;
continue;
}else{//如果有右樹，看看是葉子，還是單右。單右直接返回false
if(!p->left)
return false;
}
if(find==1 && (p->left || p->right)){//注意優(yōu)先級，&&高于||
return false;
}
}
return true;
}
判斷滿二叉樹
思路：按層遍歷二叉樹，直至發(fā)現(xiàn)第一個(gè)非滿結(jié)點(diǎn)（且必須是葉子結(jié)點(diǎn)）。在該結(jié)點(diǎn)之后的所有結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，且該結(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)是某行的行末。
實(shí)現(xiàn)：用一個(gè)plast指針來記錄上次訪問的結(jié)點(diǎn)。其他按照判完全二叉樹的方法來進(jìn)行即可。代碼未經(jīng)過驗(yàn)證就不寫了。另外，nlast更新時(shí)可以按照nlast=nlast->right來更新，這樣就不用last指針了。
擴(kuò)展：二叉樹的規(guī)則化構(gòu)建
根節(jié)點(diǎn)的值是1，其左右孩子分別是1和2，每個(gè)孩子的左右孩子依然是1和2。以此來構(gòu)建N層的二叉樹。
思路：首先需要保證N大于0.建立總根節(jié)點(diǎn)root，然后初始化p和nlast為root。然后共遍歷n-2層，每一層遍歷時(shí)都把結(jié)點(diǎn)添加左右孩子。比如n==3時(shí)，應(yīng)該遍歷中間的一層就好。
TreeNode* buildBt(int n){
if(!n)
return nullptr;
TreeNode* root=new TreeNode(1);
TreeNode *p=root,*nlast=root;
queue<TreeNode*> que;
que.push(p);
----n;
while(n){
p=que.front();
que.pop();
p->left=new TreeNode(1);
p->right=new TreeNode(2);
que.push(p->left);
que.push(p->right);
if(p==nlast->right){//如果發(fā)現(xiàn)遍歷至某一行尾，則更新n和nlast
--n;
nlast=p;
if(n<=0)
break;
}
}
return root;
}
