二叉树遍历可以分为广度遍历和深度遍历，深度遍历又可以分为前序遍历、后序遍历、中序遍历。
对于一个二叉树，如下图：
广度遍历：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);
}
};
二叉树的广度优先遍历和先序遍历有几分相似，所不同的是广度优先遍历使用一个total来记录当前二叉树节点属于那一层。
- 非递归版本：
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;
}
};
非递归版本都需要借助一个队列或者栈，将其左右孩子放入栈，自己出栈。
同样的道理，你可以实现一下二叉树的先序遍历、后续遍历、和中序遍历。
对于二叉树的算法，常用的就是递归方法，所以大家要熟练掌握递归，如果你还不了解递归，建议你从斐波拉契数列开始看起~