一、递归（实现前中后序遍历）

递归三步走：

确定函数的功能，返回值类型，形参。
确定结束条件。
确定函数等价关系。

LeetCode144：实现前序遍历
//函数功能：实现根节点为node的二叉树的遍历
void preOrder(TreeNode*node,vector<int>&vec){
        if(node==NULL)return;//循环结束条件
        vec.push_back(node->val);//中
        preOrder(node->left,vec);//左 以左子树为根节点，遍历左子树
        preOrder(node->right,vec);//右 以右子树为根节点，遍历左子树
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int>vec;
        preOrder(root,vec);
        return vec;
    }
复制代码

中后序遍历类似，只需改变输出顺序。

二、迭代（实现前中后序层序遍历）

1.前中后序遍历

以前序遍历为例：递归的本质就是栈，利用栈模拟递归调用的过程，将入栈和输出到数组操作分开。先将根节点入栈，若当前的栈顶node不为空，则进行入栈操作，按照右左的顺序入栈，空指针不入栈，再将当前节点node入栈，最后将空指针入栈，利用空指针对node进行标记，表示当前的node还未输出，入栈顺序为右左中，保证出栈顺序为中左右。若栈顶为空，则表示将空指针的栈顶出栈后新的栈顶未输出，将新栈顶出栈并输出。

LeetCode144:
vector<int> preorderTraversal(TreeNode* root) {
        vector<int>vec;
        stack<TreeNode*>stk;
        if(root)stk.push(root);//若根节点不空，现将根节点入栈
        while(!stk.empty()){
            TreeNode*node=stk.top();//取出栈顶开始遍历
            stk.pop();
            if(node){//若node不为空指针则进行入栈
                if(node->right)stk.push(node->right);//空指针不入栈 右
                if(node->left)stk.push(node->left);//空指针不入栈 左
                stk.push(node);//按照右中左的顺序入栈，则出栈顺序为左中右
                stk.push(NULL);//对node进行标记，表示该节点未遍历
            }else{//对标记的节点进行遍历
                node=stk.top();
                stk.pop();
                vec.push_back(node->val);//将标记的节点输出到数组，完成该节点的遍历
            }
        }
        return vec;
    }
复制代码

中序和后序遍历与前序遍历类似，只需改变入栈顺序即可。

2.层序遍历

利用队列实现遍历。先将根节点入队，将队首出队时，若左右节点不空则再将其左右节点入队，可以在草稿纸上画一下体会这个过程。

LeetCode102：
vector<vector<int>> levelOrder(TreeNode* root) {
       vector<vector<int>>ret;
       queue<TreeNode*>que;
       if(root)que.push(root);//将根节点入队
       while(!que.empty()){
           int size=que.size();//保存当前队列长度，后面会有入队出队操作，队列长度会变
           vector<int>vec;
           for(int i=0;i<size;i++){
               TreeNode*node=que.front();
               que.pop();
               vec.push_back(node->val);//队首出队，输出
               if(node->left)que.push(node->left);//将左右节点入队，空指针不入队
               if(node->right)que.push(node->right);
           }
           ret.push_back(vec);
       }
       return ret;
复制代码