二叉树先序遍历

定义：如果二叉树为空，则进行空操作，否则每次遍历的顺序是先根节点-->先序遍历左子树-->先序遍历右子树===>完全可以自己举例子去理解，如下图所示。
图片说明

相应代码如下：
递归版本：

void pre_search(TreeNode *root,vector<int> &vec)
{
    if(root==NULL)
        return ;
    vec.push_back(root->val);
    pre_search(root->left,vec);
    pre_search(root->right,vec);
}

迭代版本：

void pre_search(TreeNode *root,vector<int> &vec)
{
    if(root==NULL)
        return ;
    stack<TreeNode *> s;
    while(root)
    {
        vec.push_back(root->val);
        s.push(root);
        root=root->left;
    }
    while(!s.empty())
    {
        TreeNode *tmp=s.top();
        s.pop();
        tmp=tmp->right;
        while(tmp)
        {
            vec.push_back(tmp->val);
            s.push(tmp);
            tmp=tmp->left;
        }
    }
}

二叉树中序遍历

定义：如果二叉树为空，则进行空操作，否则每次遍历的顺序是先中序左节点-->根节点-->中序右节点===>完全可以自己举例子去理解，如下图所示。
图片说明
相应代码如下：
递归版本：

void mid_search(TreeNode *root,vector<int> &vec)
{
    if(root==NULL)
        return ;
    mid_search(root->left,vec);
    vec.push_back(root->val);
    mid_search(root->right,vec);
}

迭代版本：

void mid_search(TreeNode *root,vector<int> &vec)
{
    if(root==NULL)
        return ;
    stack<TreeNode *> s;
    while(root)
    {
        s.push(root);
        root=root->left;
    }
    while(!s.empty())
    {
        TreeNode *tmp=s.top();
        s.pop();
        vec.push_back(tmp->val);
        tmp=tmp->right;
        while(tmp)
        {
            s.push(tmp);
            tmp=tmp->left;
        }
    }
}

二叉树后序遍历

定义：如果二叉树为空，则进行空操作，否则每次遍历的顺序是先后序序左节点-->后序右节点-->根节点===>完全可以自己举例子去理解，如下图所示。
图片说明
递归版本：

void behind_search(TreeNode *root,vector<int> &vec)
{
    if(root==NULL)
        return ;
    behind_search(root->left,vec);
    behind_search(root->right,vec);
    vec.push_back(root->val);
}

迭代版本：
思路：
1、与前中序不同的在于，后序遍历需要有个状态量表示该结点是否是到了输出数值放入res中的时候，每一个刚放入的结点状态量一定是false，因为不知道它下面是否还有子结点（后序遍历的顺序）,只有判断了是否有子结点以后，该状态量才会变为true（无论有还是无子结点，都是会变成真的,表示可以输出数值了！），放入栈的顺序不能变，即先右结点后左结点！！（多想想后序遍历的规则就能理解）
2、两个栈，一个是用来存放结点的（便于按后序遍历的顺序存放结点），一个是状态量，存放每个对应结点的状态（是否可以输出数值！）

void behind_search(TreeNode *root,vector<int> &vec)
{
    if(root==NULL)
        return ;
    stack<TreeNode *> data;
    stack<bool> flag;
    data.push(root);
    flag.push(false);
    while(!data.empty())
    {
        TreeNode *Node=data.top();
        bool isvisit=flag.top();
        if(isvisit)
        {
            vec.push_back(Node->val);
            data.pop();
            flag.pop();
        }
        else
        {
            flag.pop();
            flag.push(true);
            if(Node->right)
            {
                data.push(Node->right);
                flag.push(false);
            }
            if(Node->left)
            {
                data.push(Node->left);
                flag.push(false);
            }
        }
    }
}

二叉树广度优先遍历（层次遍历）--bfs(breach first search)

定义：就是一层一层的从左往右的打印出元素来，直到最后一层打印完成
相应代码如下：

void bfs(Treenode *root,vector<int> vec)
{
    if(root==NULL)
        return ;
    queue<Treenode *> q;
    q.push(root);
    while(!q.empty())
    {
        int n =q.size();
        for(auto i =0;i<n;++i)
        {
            Treenode *tmp=q.front();
            q.pop();
            vec.pus_back(tmp->val);
            if(tmp->left)
                q.push(tmp->left);
            if(tmp->right)
                q.push(tmp->right);
        }
    }
}

二叉树深度优先遍历（回溯法）---递归

定义：就是每一趟都是选定一条路径（从根节点到叶子结点），打印出来以后，回溯到上一层，看是否还有别的可选路径，如果存在就再次打印出来，如果不存在就返回再上一层看是否有可选路径，直到所有的情况都遍历完全为止
回溯法心得：

  1. 首先肯定是要用到递归的！一般也是自己定义的递归函数
  2. 自定义的递归函数参数肯定需要包含存放结果的res容器、能够表示每条路径的容器tmp、跳出递归的条件，这三个内容（但不代表参数只有3个！）是肯定需要包含的，具体其他内容需根据题目要求而定