二叉樹遍歷可以分為廣度遍歷和深度遍歷，深度遍歷又可以分為前序遍歷、后序遍歷、中序遍歷脚草。
對(duì)于一個(gè)二叉樹，如下圖：
廣度遍歷：a,b,c,d,f,e,g
前序遍歷：a,b,d,e,f,g,c
后序遍歷：e,d,g,f,b,c,a
中序遍歷：d,e,b,g,f,a,c
常用的遍歷有遞歸和非遞歸版本原献，拿廣度遍歷來說：
- 遞歸版本：
class TreePrinter {
public:
vector<vector<int> > printTree(TreeNode* root) {
vector<vector<int> >res;
if(root == NULL) return res;
printTree(res,root,0);
return res;
}
void printTree(vector<vector<int>>&res,TreeNode* root,int total)//這里使用total來記錄存放在那一層
{
if(root == NULL) return;
if(res.size()==total)
res.push_back(vector<int>());
res[total].push_back(root->val);
printTree(res,root->left,total+1);
printTree(res,root->right,total+1);
}
};
二叉樹的廣度優(yōu)先遍歷和先序遍歷有幾分相似馏慨，所不同的是廣度優(yōu)先遍歷使用一個(gè)total來記錄當(dāng)前二叉樹節(jié)點(diǎn)屬于那一層埂淮。
- 非遞歸版本：
class TreePrinter {
public:
vector<vector<int> > printTree(TreeNode* root) {
// write code here
vector<vector<int>> result;
result.resize(500);
queue<TreeNode*> q;
int last, nlast, layer=0;
q.push(root);
last = root->val;
while(!q.empty())
{
TreeNode* t = q.front();
result[layer].push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
if(t->val == last) layer++, last = q.back()->val;
q.pop();
}
result.resize(layer);
return result;
}
};
非遞歸版本都需要借助一個(gè)隊(duì)列或者棧，將其左右孩子放入棧写隶，自己出棧倔撞。
同樣的道理，你可以實(shí)現(xiàn)一下二叉樹的先序遍歷慕趴、后續(xù)遍歷痪蝇、和中序遍歷。
對(duì)于二叉樹的算法冕房，常用的就是遞歸方法躏啰，所以大家要熟練掌握遞歸，如果你還不了解遞歸耙册，建議你從斐波拉契數(shù)列開始看起~