二叉樹遍歷

二叉樹的遍歷主要有四種：

前序、中序、后序和層序

---

遍歷的實(shí)現(xiàn)方式主要是：

遞歸和非遞歸

遞歸遍歷的實(shí)現(xiàn)非常容易，非遞歸的實(shí)現(xiàn)需要用到棧，難度系數(shù)要高一點(diǎn)。

1.二叉樹節(jié)點(diǎn)的定義

二叉樹的每個節(jié)點(diǎn)由節(jié)點(diǎn)值、左子樹和右子樹組成。

class TreeNode{ public:int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} }

2.二叉樹的遍歷方式

前序遍歷：先訪問根節(jié)點(diǎn)，再訪問左子樹，最后訪問右子樹

中序遍歷：先訪問左子樹，再訪問根節(jié)點(diǎn)，最后訪問右子樹

后序遍歷：先訪問左子樹，再訪問右子樹，最后訪問根節(jié)點(diǎn)

層序遍歷：每一層從左到右訪問每一個節(jié)點(diǎn)。

舉例說明:(以下面的二叉樹來說明這四種遍歷)

前序遍歷：ABDFGHIEC
中序遍歷：FDHGIBEAC
后序遍歷：FHIGDEBCA
層序遍歷：ABCDEFGHI

3.前序遍歷

遞歸版本

按照遍歷的
順序很容易就能寫出下列代碼：

以下代碼均在leetcode測試通過，二叉樹前序遍歷的原題鏈接：戳我！leetcode直通車！上車?yán)?#xff01;

vector<int> preorderTraversal(TreeNode* root){vector<int> ret;dfsPreOrder(root,ret);return ret; } void dfsPreOrder(TreeNode* root,vector<int> &ret){if(root==NULL) return;ret.push_back(root->val);//存儲根節(jié)點(diǎn)if(root->left!=NULL) dfsPreOrder(root->left,ret);//訪問左子樹if(root->right!=NULL) dfsPreOrder(root->right,ret);//訪問右子樹 }

非遞歸版本

非遞歸版本需要利用輔助棧來實(shí)現(xiàn)

1.首先把根節(jié)點(diǎn)壓入棧中
2.此時棧頂元素即為當(dāng)前根節(jié)點(diǎn)，彈出并訪問即可
3.把當(dāng)前根節(jié)點(diǎn)的右子樹和左子樹分別入棧，考慮到棧是先進(jìn)后出，所以必須右子樹先入棧，左子樹后入棧
4.重復(fù)2,3步驟，直到棧為空為止

vector<int> preorderTraversal(TreeNode* root) {vector<int> ret;if (root==NULL) return ret;stack<TreeNode*> st;st.push(root);while(!st.empty()){TreeNode* tp = st.top();//取出棧頂元素st.pop();ret.push_back(tp->val);//先訪問根節(jié)點(diǎn)if(tp->right!=NULL) st.push(tp->right);//由于棧時先進(jìn)后出，考慮到訪問順序，先將右子樹壓棧if(tp->left!=NULL) st.push(tp->left);//將左子樹壓棧}return ret; }

4.中序遍歷

遞歸版本

中序遍歷的訪問順序依次是左子樹->根節(jié)點(diǎn)->右子樹，按照遞歸的思想依次訪問即可

以下代碼均在leetcode測試通過，二叉樹中序遍歷的原題鏈接：戳我！leetcode直通車！上車?yán)?#xff01;

vector<int> inorderTraversal(TreeNode* root) {vector<int> ret;inorder(root,ret);return ret; } void inorder(TreeNode* p,vector<int>& ret) {if(p==NULL) return;inorder(p->left,ret);//訪問左子樹ret.push_back(p->val);//訪問根節(jié)點(diǎn)inorder(p->right,ret);//訪問右子樹 }

非遞歸版本

中序遍歷的非遞歸版本比前序稍微復(fù)雜一點(diǎn)，除了用到輔助棧之外，還需要一個指針p指向下一個待訪問的節(jié)點(diǎn)

如果p非空，則將p入棧，p指向p的左子樹
如果p為空，說明此時左子樹已經(jīng)訪問到盡頭了，彈出當(dāng)前棧頂元素，進(jìn)行訪問，并把p設(shè)置成p的右子樹的左子樹，即下一個待訪問的節(jié)點(diǎn)

vector<int> inorderTraversal(TreeNode* root) {vector<int> ret;TreeNode* p = root;stack<TreeNode*> st;while(!st.empty()||p!=NULL){if(p){//p非空，代表還有左子樹，繼續(xù)st.push(p);p=p->left;}else{//如果為空，代表左子樹已經(jīng)走到盡頭了p = st.top();st.pop();ret.push_back(p->val);//訪問棧頂元素if(p->right) {st.push(p->right);//如果存在右子樹，將右子樹入棧p = p->right->left;//p始終為下一個待訪問的節(jié)點(diǎn)}else p=NULL;}}return ret; }

5.后序遍歷

遞歸版本

遞歸版本還是一樣，按照訪問順序來寫代碼即可。

以下代碼均在leetcode測試通過，二叉樹后序遍歷的原題鏈接：戳我！leetcode直通車！上車?yán)?#xff01;

vector<int> inorderTraversal(TreeNode* root) {vector<int> ret;inorder(root,ret);return ret;} void inorder(TreeNode* p,vector<int>& ret) {if(p==NULL) return;inorder(p->left,ret);//訪問左子樹inorder(p->right,ret);//訪問右子樹ret.push_back(p->val);//訪問根節(jié)點(diǎn) }

非遞歸版本

采用一個輔助棧和兩個指針p和r，p代表下一個需要訪問的節(jié)點(diǎn)，r代表上一次需要訪問的節(jié)點(diǎn)

1、如果p非空，則將p入棧，p指向p的左子樹

2、如果p為空，代表左子樹到了盡頭，此時判斷棧頂元素

如果棧頂元素存在右子樹且沒有被訪問過(等于r代表被訪問過)，則右子樹入棧，p指向右子樹的左子樹
如果棧頂元素不存在或者已經(jīng)被訪問過，則彈出棧頂元素，訪問，然后p置為null，r記錄上一次訪問的節(jié)點(diǎn)p

vector<int> postorderTraversal(TreeNode* root) {vector<int> ret;TreeNode* p = root;stack<TreeNode*> st;TreeNode* r = NULL;while(p||!st.empty()){if(p){st.push(p);p = p -> left;}else{p = st.top();if(p->right&&p->right!=r){p = p->right;st.push(p);p = p->left;}else {p = st.top();st.pop();ret.push_back(p->val);r= p;p = NULL;}}}return ret; }

還有另一種解法，大家可以看看前序遍歷的非遞歸版本，訪問順序依次是根節(jié)點(diǎn)->左子樹->右子樹，如果將壓棧順序改動一下，可以很容易得到根節(jié)點(diǎn)->右子樹->左子樹，觀察這個順序和后序遍歷左子樹->右子樹->根節(jié)點(diǎn)正好反序。

vector<int> postorderTraversal(TreeNode* root) {vector<int> ret;if(root==NULL) return ret;stack<TreeNode*> st;st.push(root);while(!st.empty()){TreeNode* tmp = st.top();ret.push_back(tmp->val);//先訪問根節(jié)點(diǎn)st.pop();if(tmp->left!=NULL) st.push(tmp->left);//再訪問左子樹if(tmp->right!=NULL) st.push(tmp->right);//最后訪問右子樹}reverse(ret.begin(),ret.end());//將結(jié)果反序輸出return ret; }

6.層序遍歷

層序遍歷，即按層序從左到右輸出二叉樹的每個節(jié)點(diǎn)。如例子中的A(第一層)BC(第二層)DE(第三層)FG(第四層)HI(第五層)

層序遍歷需要借助隊(duì)列queue來完成，因?yàn)橐獫M足先進(jìn)先去的訪問順序。具體思路看代碼：

以下代碼均在leetcode測試通過，二叉樹層序遍歷的原題鏈接：戳我！leetcode直通車！上車?yán)?#xff01;

vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ret;if(root==NULL) return ret;queue<TreeNode*> que;que.push(root);while(!que.empty()){vector<int> temp;queue<TreeNode*> tmpQue;//存儲下一層需要訪問的節(jié)點(diǎn)while(!que.empty())//從左到右依次訪問本層{TreeNode* tempNode = que.front();que.pop();temp.push_back(tempNode->val);if(tempNode->left!=NULL) tmpQue.push(tempNode->left);//左子樹壓入隊(duì)列if(tempNode->right!=NULL) tmpQue.push(tempNode->right);//右子樹壓入隊(duì)列}ret.push_back(temp);que=tmpQue;//訪問下一層}return ret; }

7.其他經(jīng)典考題

根據(jù)前序和中序遍歷來構(gòu)造二叉樹

前序遍歷的順序是：根節(jié)點(diǎn)->左子樹->右子樹，中序遍歷的順序時：左子樹->根節(jié)點(diǎn)->右子樹。

在前序遍歷中第一個節(jié)點(diǎn)為根節(jié)點(diǎn)，然后去中序遍歷中找到根節(jié)點(diǎn)，則其左邊為左子樹，右邊為右子樹

例如前序遍歷ABC，中序遍歷BAC,在前序遍歷中找到根節(jié)點(diǎn)A，在中序遍歷中A的左邊B為左子樹，右邊C為右子樹。

然后一次遞歸下去，就可以把整棵數(shù)構(gòu)造出來了。

以下代碼均在leetcode測試通過，構(gòu)造二叉樹的原題鏈接：戳我！leetcode直通車！上車?yán)?#xff01;

typedef vector<int>::iterator vi; TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.empty()||inorder.empty()) return (TreeNode*)NULL;vi preStart = preorder.begin();vi preEnd = preorder.end()-1;vi inStart = inorder.begin();vi inEnd = inorder.end()-1;return constructTree(preStart,preEnd,inStart,inEnd); } TreeNode* constructTree(vi preStart,vi preEnd,vi inStart,vi inEnd) {if(preStart>preEnd||inStart>inEnd) return NULL;//前序遍歷的第一個節(jié)點(diǎn)為根節(jié)點(diǎn)TreeNode* root = new TreeNode(*preStart);if(preStart==preEnd||inStart==inEnd) return root;vi rootIn = inStart;while(rootIn!=inEnd){//在中序遍歷中找到根節(jié)點(diǎn)if(*rootIn==*preStart) break;else ++rootIn;}root->left = constructTree(preStart+1,preStart+(rootIn-inStart),inStart,rootIn-1);//遞歸構(gòu)造左子樹root->right = constructTree(preStart+(rootIn-inStart)+1,preEnd,rootIn+1,inEnd);//遞歸構(gòu)造右子樹return root; }

根據(jù)中序和后序遍歷構(gòu)造二叉樹

與上面的題目比較相似，后序遍歷中最后一個節(jié)點(diǎn)為根節(jié)點(diǎn)，然后在中序遍歷中找到根節(jié)點(diǎn)，左邊為左子樹，右邊為右子樹。

以下代碼均在leetcode測試通過，構(gòu)造二叉樹的原題鏈接：戳我！leetcode直通車！上車?yán)?#xff01;

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(inorder.empty()||postorder.empty()) return NULL;return constructTree(inorder,postorder,0,inorder.size()-1,0,postorder.size()-1); } TreeNode* constructTree(vector<int>& inorder, vector<int>& postorder, int inStart,int inEnd,int postStart,int postEnd) {if(postStart>postEnd||inStart>inEnd) return NULL;TreeNode* root = new TreeNode(postorder[postEnd]);if(postStart==postEnd||inStart==inEnd) return root;int i ;for(i = inStart ;i<inEnd;i++)//在中序遍歷中找到根節(jié)點(diǎn){if(inorder[i]==postorder[postEnd]) break;}root->left = constructTree(inorder,postorder,inStart,i-1,postStart,postStart+i-inStart-1);//遞歸構(gòu)造左子樹root->right = constructTree(inorder,postorder,i+1,inEnd,postStart+i-inStart,postEnd-1);//遞歸構(gòu)造右子樹return root; }

求二叉樹的深度

采用深度優(yōu)先搜索，可以很容易計(jì)算出深度

以下代碼均在leetcode測試通過，二叉樹的深度的原題鏈接：戳我！leetcode直通車！上車?yán)?#xff01;

int maxDepth(TreeNode* root) {return DfsTree(root); } int DfsTree(TreeNode* root){if(root==NULL) return 0;int left = DfsTree(root->left);//左子樹的深度int right = DfsTree(root->right);//右子樹的深度return left>right?left+1:right+1;//比較左右子樹的深度，取最大值 }

判斷是否為平衡二叉樹

利用上面求深度的思想，求出左右子樹的深度，判斷它們相差是否大于1，如果大于則返回false。

以下代碼均在leetcode測試通過，判斷平衡二叉樹的原題鏈接：戳我！leetcode直通車！上車?yán)?#xff01;

bool isBalanced(TreeNode* root) {return dfsTree(root)!=-1; } int dfsTree(TreeNode* root) {if(root==NULL) return 0;int left = dfsTree(root->left);//求左子樹的深度if(left == -1) return -1;//返回-1代表左子樹不平衡int right = dfsTree(root->right);//求右子樹的深度if(right== -1) return -1;//返回-1代表右子樹不平衡if(abs(left-right)>1) return -1;//如果左右子樹均平衡，則判斷它們是否相差小于等于1return max(left,right)+1;//返回該根節(jié)點(diǎn)樹的深度 }

原博客地址：http://blog.csdn.net/terence1212/article/details/52182836

總結(jié)

以上是生活随笔為你收集整理的全面剖析【二叉树】的各类遍历方法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。