题目链接：
二叉树遍历（Traversing binary tree)
常见的有三种遍历方式：
- 前序遍历（Pre-Order Traverse)：若二叉树为空，返回空操作；否则先访问根节点，然后前序遍历左子树，再前序遍历右子数。
- 中序遍历（In-Order Traverse)：若二叉树为空，返回空操作；否则从根节点开始，先中序遍历左子树，再访问根节点，最后中序遍历右子树
- 后序遍历（Post-Order Traverse):若二叉树为空，返回空操作；否则先遍历左子树，再遍历右子树，最后访问根节点。
递归实现
二叉树的定义是用递归的形式，所以实现遍历算法用递归是很自然的。
代码很简洁。
前序遍历
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution{
public:
vector<int> preorderTraversal(TreeNode *root){
vector<int> result;
result.clear();
if(root==NULL)
return result;
result.push_back(root->val);//访问根节点，不同遍历只是这句话的位置不一样
preorderTraversal(root->left);
preorderTraversal(root->right);
return result;
}
};
中序遍历
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> result;
void inorder(TreeNode *root){
if(root==NULL) return;
inorder(root->left);
result.push_back(root->val);
inorder(root->right);
}
vector<int> inorderTraversal(TreeNode *root) {
inorder(root);
return result;
}
};
后序遍历
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> result;
void postorder(TreeNode *root){
if(root==NULL) return;
postorder(root->left);
postorder(root->right);
result.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode *root) {
postorder(root);
return result;
}
};
二叉树遍历的非递归实现
leetcode上还是希望我们用非递归的方式(迭代法）实现，而和递归关系最紧密的就是栈结构了。
前序遍历
前序遍历的规则是：根节点->左子树->右子树。在设计程序时，先把根节点压入栈，由于在前序遍历中，根节点是先于左右子树访问的，所以root的value先弹出(pop)，并加入访问序列result；然后不断压入右子树，直到叶节点；再压入右子树，直到叶节点;最后弹出，直到栈为空。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
vector<int> result;
result.clear();
if(root==NULL)
return result;
stack<TreeNode *> my_stack;
my_stack.push(root);//把根节点压入栈
while(!my_stack.empty()){
TreeNode *top=my_stack.top();
result.push_back(top->val);
my_stack.pop();
if(top->right!=NULL)
my_stack.push(top->right);//先把右子树压入栈，因为右子树后出来
if(top->left!=NULL)
my_stack.push(top->left);//再把左子树入栈
}
return result;
}
};
中序遍历
中序遍历的规则是：左子树->根节点->右子树。我们可以先把根节点root压入栈my_stack。进入一个循环while,循环的条件是遍历指针p不为空或者栈不为空，然后把遍历左子树p->left，并压入栈push，当遍历到叶节点时，进入出栈循环，弹出栈首元素top，加入访问序列result,并访问其右节点p->right并压入栈。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> result;
result.clear();
stack<TreeNode *> my_stack;
TreeNode *p=root;
if(root==NULL)
return result;
while(p||!my_stack.empty()){
while(p){
my_stack.push(p);
p=p->left;
}
if(!my_stack.empty()){
TreeNode *top=my_stack.top();
my_stack.pop();
result.push_back(top->val);
p=top->right;
}
}
return result;
}
};
后序遍历
与前序和中序遍历相比，后序遍历的迭代法相对难一些。
后序遍历的规则是左子树->右子树->根节点，左右子树先于根节点输出。根据这里特性，我们可以设置两个指针cur和pre,cur指向当前栈顶结点，pre是上次输出的元素，如果cur的存在左右子树，则cur按先右后左顺序入栈。弹出条件：如果cur没有左右子树（即为叶子结点），那么弹出；如果出现pre是cur的左子树或者右子树，说明此时已经处于回溯状态，弹出栈顶元素，并更新pre。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> result;
result.clear();
if(root==NULL)
return result;
stack<TreeNode *> my_stack;
my_stack.push(root);//把根节点压入栈
TreeNode *cur=root,*pre=NULL;
while(!my_stack.empty()){
cur=my_stack.top();
if(!cur->left&&!cur->right||(pre&&(cur->left==pre||cur->right==pre))){
result.push_back(cur->val);
my_stack.pop();
pre=cur;
}else{
if(cur->right){
my_stack.push(cur->right);
}
if(cur->left){
my_stack.push(cur->left);
}
}
}
return result;
}
};