二叉树前序中序后序层序遍历总结
相关题目
- No. 144 二叉树的前序遍历
- No. 94 二叉树的中序遍历
- No. 145 二叉树的后序遍历
- No. 102 二叉树的层序遍历
解法总结
关于二叉树遍历的概念不再赘述,直接开始怼题目。
先对前序遍历、中序遍历和后序遍历做总结,层序遍历拎出来单独说。
关于二叉树的定义如下:
1 2 3 4 5 6 7 8
| 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) {} };
|
递归解法
前序遍历
1 2 3 4 5 6 7
| void preOrderRecur(TreeNode* root,vector<int>&res) { if(root==nullptr) return; res.push_back(root->val); preOrderRecur(root->left,res); preOrderRecur(root->right,res); }
|
中序遍历
1 2 3 4 5 6 7 8
| void inOrderRecur(TreeNode* root,vector<int>&res) { if(root==nullptr) return; inOrderRecur(root->left,res); res.push_back(root->val); inOrderRecur(root->right,res); }
|
后序遍历
1 2 3 4 5 6 7
| void postOrderRecur(TreeNode* root,vector<int>&res) { if(root==nullptr) return; postOrderRecur(root->left,res); postOrderRecur(root->right,res); res.push_back(root->val); }
|
迭代解法
迭代解法的核心就是用一个栈去模拟递归过程中的系统栈,可以加深我们对递归具体过程的理解。
前序遍历
前序遍历就是中结点随进随出,右结点先于左结点压入栈。然后栈中会记录应该回溯的路径信息,每次弹出栈的顶结点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| void preOrderIteration(TreeNode* root,vector<int>&res) { if(root==nullptr) return ; stack<TreeNode*>st; st.push(root); while(!st.empty()) { TreeNode* node=st.top(); st.pop(); res.push_back(node->val); if(node->right) st.push(node->right); if(node->left) st.push(node->left); } }
|
中序遍历
中序遍历由于中间结点先不输出,所以得有一个指针来帮助访问结点,栈同样保存了回溯时的位置信息。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| void inOrderIteration(TreeNode* root,vector<int>&res) { if(root==nullptr) return ; stack<TreeNode*>st; TreeNode* cur=root; while(cur!=nullptr||!st.empty()) { if(cur!=nullptr) { st.push(cur); cur=cur->left; //左 } else{ cur=st.top(); st.pop(); res.push_back(cur->val);//中 cur=cur->right;//右 } } }
|
后序遍历
后序遍历可以由先序遍历稍微改动得到。后序遍历的顺序是左右中,先序遍历的顺序是中左右,可以先调换左右顺序,得到中右左,然后颠倒结果数组即可得到答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| void postOrderIteration(TreeNode* root,vector<int>&res) { if(root==nullptr) return ; stack<TreeNode*>st; st.push(root); while(!st.empty()) { TreeNode* node=st.top(); st.pop(); if(node->left) st.push(node->left); if(node->right) st.push(node->right); } reverse(res.begin(),res.end()); }
|
层序遍历
BFS常规解法
方法不再详述。给出两种不同输出格式的代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| void levelOrder(TreeNode* root,vector<vector<int>>&res) { if(root==nullptr) return ; queue<TreeNode*>q; q.push(root); while(!q.empty()) { int size=q.size(); vector<int>level; for(int i=0;i<size;i++) { TreeNode* cur=q.front(); q.pop(); if(!cur) continue; level.push_back(cur->val); q.push(cur->left); q.push(cur->right); } if(level.size()>0) res.push_back(level); } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| void levelOrder_single(TreeNode* root,vector<int>&res) { if(root==nullptr) return ; queue<TreeNode*>q; q.push(root); while(!q.empty()) { int size=q.size(); for(int i=0;i<size;i++) { TreeNode* cur=q.front(); q.pop(); if(!cur) continue; res.push_back(cur->val); q.push(cur->left); q.push(cur->right); } } }
|
DFS递归解法
DFS递归解法就是使用level变量来记录二叉树的层数,只有相同的层,才将对应结点的值加入相应的vector中。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| void levelOrder_DFS(TreeNode* root,vector<vector<int>>&res,int level) { if(root==nullptr) return ; if(level>=res.size()) res.push_back(vector<int>()); res[level].push_back(root->val); levelOrder_DFS(root->left,res,level+1); levelOrder_DFS(root->right,res,level+1); }
vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>>res; levelOrder_DFS(root,res,0); return res; }
|