全面剖析树的各类遍历方法

xiaoxiao2021-02-28 56

面试中常考到树的前序，中序，后序和层序遍历，这篇博文就带你深度剖析一下二叉树的各类遍历算法的实现

二叉树的遍历主要有四种，前序、中序、后序和层序

遍历的实现方式主要是：递归和非递归

递归遍历的实现非常容易，非递归的实现需要用到栈，难度系数要高一点。

一、二叉树节点的定义

二叉树的每个节点由节点值、左子树和右子树组成。

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

二、二叉树的遍历方式

前序遍历：先访问根节点，再访问左子树，最后访问右子树

中序遍历：先访问左子树，再访问根节点，最后访问右子树

后序遍历：先访问左子树，再访问右子树，最后访问根节点

层序遍历：每一层从左到右访问每一个节点。

举例说明:(以下面的二叉树来说明这四种遍历)

前序遍历：ABDFGHIEC中序遍历：FDHGIBEAC后序遍历：FHIGDEBCA层序遍历：ABCDEFGHI

大家可以根据这个例子先熟悉一下这四种遍历，如有不懂的，建议先去google一下，再接着阅读本文

三、前序遍历

递归版本

按照遍历的顺序很容易就能写出下列代码：

以下代码均在leetcode测试通过，二叉树前序遍历的原题链接：戳我！leetcode直通车！上车啦！

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); //存储根节点 if(root->left!= NULL) dfsPreOrder(root->left,ret); //访问左子树 if(root->right!= NULL) dfsPreOrder(root->right,ret); //访问右子树 }

非递归版本

非递归版本需要利用辅助栈来实现

1.首先把根节点压入栈中2.此时栈顶元素即为当前根节点，弹出并访问即可3.把当前根节点的右子树和左子树分别入栈，考虑到栈是先进后出，所以必须右子树先入栈，左子树后入栈4.重复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); //先访问根节点 if(tp->right!= NULL) st.push(tp->right); //由于栈时先进后出，考虑到访问顺序，先将右子树压栈 if(tp->left!= NULL) st.push(tp->left); //将左子树压栈 } return ret; }

四、中序遍历

递归版本

中序遍历的访问顺序依次是左子树->根节点->右子树，按照递归的思想依次访问即可

以下代码均在leetcode测试通过，二叉树中序遍历的原题链接：戳我！leetcode直通车！上车啦！

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); //访问根节点 inorder(p->right,ret); //访问右子树 }

非递归版本

中序遍历的非递归版本比前序稍微复杂一点，除了用到辅助栈之外，还需要一个指针p指向下一个待访问的节点

如果p非空，则将p入栈，p指向p的左子树如果p为空，说明此时左子树已经访问到尽头了，弹出当前栈顶元素，进行访问，并把p设置成p的右子树的左子树，即下一个待访问的节点 vector< int> inorderTraversal(TreeNode* root) { vector< int> ret; TreeNode* p = root; stack<TreeNode*> st; while(!st.empty()||p!= NULL){ if(p){ //p非空，代表还有左子树，继续 st.push(p); p=p->left; } else{ //如果为空，代表左子树已经走到尽头了 p = st.top(); st.pop(); ret.push_back(p->val); //访问栈顶元素 if(p->right) { st.push(p->right); //如果存在右子树，将右子树入栈 p = p->right->left; //p始终为下一个待访问的节点 } else p= NULL; } } return ret; }

五、后序遍历

递归版本

递归版本还是一样，按照访问顺序来写代码即可。

以下代码均在leetcode测试通过，二叉树后序遍历的原题链接：戳我！leetcode直通车！上车啦！

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); //访问根节点 }

非递归版本

采用一个辅助栈和两个指针p和r，p代表下一个需要访问的节点，r代表上一次需要访问的节点

1、如果p非空，则将p入栈，p指向p的左子树

2、如果p为空，代表左子树到了尽头，此时判断栈顶元素

如果栈顶元素存在右子树且没有被访问过(等于r代表被访问过)，则右子树入栈，p指向右子树的左子树如果栈顶元素不存在或者已经被访问过，则弹出栈顶元素，访问，然后p置为null，r记录上一次访问的节点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; }

还有另一种解法，大家可以看看前序遍历的非递归版本，访问顺序依次是根节点->左子树->右子树，如果将压栈顺序改动一下，可以很容易得到根节点->右子树->左子树，观察这个顺序和后序遍历左子树->右子树->根节点正好反序。

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); //先访问根节点 st.pop(); if(tmp->left!= NULL) st.push(tmp->left); //再访问左子树 if(tmp->right!= NULL) st.push(tmp->right); //最后访问右子树 } reverse(ret.begin(),ret.end()); //将结果反序输出 return ret; }

六、层序遍历

层序遍历，即按层序从左到右输出二叉树的每个节点。如例子中的A(第一层)BC(第二层)DE(第三层)FG(第四层)HI(第五层)

层序遍历需要借助队列queue来完成，因为要满足先进先去的访问顺序。具体思路看代码：

以下代码均在leetcode测试通过，二叉树层序遍历的原题链接：戳我！leetcode直通车！上车啦！

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; //存储下一层需要访问的节点 while(!que.empty()) //从左到右依次访问本层 { TreeNode* tempNode = que.front(); que.pop(); temp.push_back(tempNode->val); if(tempNode->left!= NULL) tmpQue.push(tempNode->left); //左子树压入队列 if(tempNode->right!= NULL) tmpQue.push(tempNode->right); //右子树压入队列 } ret.push_back(temp); que=tmpQue; //访问下一层 } return ret; }

七、其他经典考题

根据前序和中序遍历来构造二叉树

前序遍历的顺序是：根节点->左子树->右子树，中序遍历的顺序时：左子树->根节点->右子树。

在前序遍历中第一个节点为根节点，然后去中序遍历中找到根节点，则其左边为左子树，右边为右子树

例如前序遍历ABC，中序遍历BAC,在前序遍历中找到根节点A，在中序遍历中A的左边B为左子树，右边C为右子树。

然后一次递归下去，就可以把整棵数构造出来了。

以下代码均在leetcode测试通过，构造二叉树的原题链接：戳我！leetcode直通车！上车啦！

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; //前序遍历的第一个节点为根节点 TreeNode* root = new TreeNode(*preStart); if(preStart==preEnd||inStart==inEnd) return root; vi rootIn = inStart; while(rootIn!=inEnd){ //在中序遍历中找到根节点 if(*rootIn==*preStart) break; else ++rootIn; } root->left = constructTree(preStart+ 1,preStart+(rootIn-inStart),inStart,rootIn -1); //递归构造左子树 root->right = constructTree(preStart+(rootIn-inStart)+ 1,preEnd,rootIn+ 1,inEnd); //递归构造右子树 return root; }

根据中序和后序遍历构造二叉树

与上面的题目比较相似，后序遍历中最后一个节点为根节点，然后在中序遍历中找到根节点，左边为左子树，右边为右子树。

以下代码均在leetcode测试通过，构造二叉树的原题链接：戳我！leetcode直通车！上车啦！

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++) //在中序遍历中找到根节点 { if(inorder[i]==postorder[postEnd]) break; } root->left = constructTree(inorder,postorder,inStart,i -1,postStart,postStart+i-inStart -1); //递归构造左子树 root->right = constructTree(inorder,postorder,i+ 1,inEnd,postStart+i-inStart,postEnd -1); //递归构造右子树 return root; }

求二叉树的深度

采用深度优先搜索，可以很容易计算出深度

以下代码均在leetcode测试通过，二叉树的深度的原题链接：戳我！leetcode直通车！上车啦！

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直通车！上车啦！

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; //如果左右子树均平衡，则判断它们是否相差小于等于1 return max(left,right)+ 1; //返回该根节点树的深度 }

本篇博客到这里就结束了，当然二叉树的变种考题还有很多中，后序也会陆续收集进来，敬请关注我的小站。

如有任何疑问，可以在下方留言去留言，也可以直接发邮件给我,详见联系方式

转载请注明原文地址: https://www.6miu.com/read-2621341.html

技术

最新回复(0)