原文链接;【LeetCode学习计划】《数据结构入门-C++》第10天 树_Wang_Xin_Ling的博客-CSDN博客 

方法1：递归

树的遍历过程中，在进入到左孩子和右孩子后，还需要按照同样的遍历顺序去遍历，直到遍历整棵树，因此遍历的过程是一个非常典型的递归过程。

144. 二叉树的前序遍历

#include <vector>
using namespace std;
class Solution
{
public:
    vector<int> preorderTraversal(TreeNode *root)
    {
        vector<int> ans;
        preorder(root, ans);
        return ans;
    }
    void preorder(TreeNode *root, vector<int> &ans)
    {
        if (!root)
            return;
        ans.push_back(root->val);
        preorder(root->left, ans);
        preorder(root->right, ans);
    }
};

 94. 二叉树的中序遍历

#include <vector>
using namespace std;
class Solution
{
public:
    vector<int> inorderTraversal(TreeNode *root)
    {
        vector<int> ans;
        inorder(root, ans);
        return ans;
    }
    void inorder(TreeNode *root, vector<int> &ans)
    {
        if (!root)
            return;

        inorder(root->left, ans);
        ans.push_back(root->val);
        inorder(root->right, ans);
    }
};

 145. 二叉树的后序遍历

#include <vector>
using namespace std;
class Solution
{
public:
    vector<int> postorderTraversal(TreeNode *root)
    {
        vector<int> ans;
        postorder(root, ans);
        return ans;
    }
    void postorder(TreeNode *root, vector<int> &ans)
    {
        if (!root)
            return;
        postorder(root->left, ans);
        postorder(root->right, ans);
        ans.push_back(root->val);
       
    }
};

方法2：迭代
我们可以把递归过程中隐式维护的栈具象出来。

对于前序遍历，我们在进入任意子树时，需要先对当前结点操作 doSomething()，然后访问它的左孩子 p = p->left；如果左孩子不是空结点，则要进入以左孩子为根节点的子树，重复操作while(p)。因此从栈中拿出一个根节点后，先要一直往左走，直到左孩子为空后，才访问右孩子。同理，进入右孩子后也要将它作为根节点往左进发。详见如下代码结构。
 

if (!root)
    return {};

TreeNode *p = root;
stk.push(root);
while (!stk.empty())
{
    while (p)
    {
        doSomething();
        stk.push(p);
        p = p->left;
    }
    p = stk.top();
    stk.pop();
    p = p->right;
}

对于中序遍历，我们则要先一直往左走p = p->left，直到左孩子为空后，再对当前结点操作doSomething()，然后紧接着就是访问右孩子p = p->right。详见如下代码结构。

if (!root)
    return {};

TreeNode *p = root;
while (!stk.empty())
{
    while (p)
    {
        stk.push(p);
        p = p->left;
    }
    p = stk.top();
    stk.pop();
    doSomething();
    p = p->right;
}

对于后序遍历，它的代码会稍微多一点。因为在一直往左走后p = p->left（每次往左走之前将根节点压入栈），需要再从栈顶拿出根节点stk.pop()，先去访问右孩子p = p->right，将右孩子压入栈后进行以它为根节点的新一轮循环。

假设右孩子的子树遍历完了（不管如何就是遍历完了），现在回到了刚刚的根节点。但此时根节点有右孩子，这一次又会把右孩子压入栈，然后去访问右孩子的子树。所以我们需要一个额外的变量lastRight。当右孩子遍历完成后（在右孩子子树中，右孩子为p），设lastRight=p。从右孩子回来后，根节点为p，右孩子为p->right，这时我们判断一次p->right是否等于lastRight。如果等于就不用进入右孩子。

右孩子遍历完成，是时候对根节点操作了doSomething()。然后就直接从栈中再取结点。因为所有根节点的左孩子和右孩子已经在之前就压入栈了。
 

if (!root)
    return {};

TreeNode *p = root, *lastRight = nullptr;
while (p || !stk.empty())
{
    while (p)
    {
        stk.push(p);
        p = p->left;
    }
    p = stk.top();
    stk.pop();
    if (!p->right || p->right == lastRight)
    {
        ans.emplace_back(p->val);
        lastRight = p;
        p = nullptr;
    }
    else
    {
        stk.push(p);
        p = p->right;
    }
}