前序遍历

对根节点，左右子树采取根左右的顺序进行遍历。

递归

void preorderTraversal(TreeNode* root) {
  if(!root) return ;
   visit(root);
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

非递归

    vector<int> preorderTraversal(TreeNode* root) {
       vector<int>res;
       stack<TreeNode*>s;//使用栈来存储节点
       auto p=root;
       while(p||!s.empty()){//二者有一个满足循环就可以继续
            while(p){ //先访问根节点，访问完之后再入栈
                res.push_back(p->val);
                s.push(p);
                p=p->left;
            }
            p=s.top();
            s.pop();
            //弹出栈顶结点，开始遍历其右子树
            p=p->right;
       }
       return res;
    }

中序遍历

左根右的顺序

递归

void inorderTraversal(TreeNode* root) {
  if(!root) return ;
  inorderTraversal(root->left);
  visit(root);
  inorderTraversal(root->right);
}

非递归

  vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> ss;
        auto p=root;
        while(!ss.empty()||p){
            while(p){
                 ss.push(p);
                p=p->left;
            }
            p=ss.top();
            ss.pop();
            res.push_back(p->val);  //对根节点的访问放在其左子树之后，前序和中序的区别就在这里。
            p=p->right;
        }
        return res;
    }

后序遍历

左右根的顺序

递归

void postorderTraversal(TreeNode* root) {
  if(!root) return ;
  postorderTraversal(root->left);
  postorderTraversal(root->right);
   visit(root);
}

非递归

后序遍历比起前两种又复杂一点点，因为你在访问到根节点的时候无法判断它的右子树是否已经遍历完，

  vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> ss;
        auto p=root;
        TreeNode* pre=nullptr;//设置一个前置指针，指向遍历的上一个结点
        while(!ss.empty()||p){
            while(p){
                 ss.push(p);
                p=p->left;
            }
            p=ss.top();
          if(p->right==nullptr||p->right==pre){ //在这里判断右子树有没有遍历完毕，若已遍历完，则访问当前节点。
              res.push_back(p->val);
              ss.pop();
              pre=p;
              p=nullptr;//p指针需要置空，确保循环可以正确退出
          }
           else  
            p=p->right;
        }
        return res;
    }

层次遍历

对同一层次的结点，从左至右依次输出，使用队列很方便

一次性遍历

    vector<int> levelOrder(Node* root) {
        vector<int>res;
      if(!root) return res;
       queue<Node*>q;
       Node *t;
       q.push(root);
       while(!q.empty()){
               t=q.front(); 
               q.pop();
          res.push_back(t->val);
         if(t->left) q.push(t->left);
         if(t->right) q.push(t->right);
    }
       return res;     
    }

分层遍历，也就是要把每一层分开

  vector<vector<int>> levelOrder(TreeNode* root) { //返回一个二维数组
        vector<vector<int>>res;
                if(!root) return res;
        queue<TreeNode*>q;
        q.push(root);
        int levelnum=0;//下一层结点的数目
        int level=1;//当前层节点的数目
        vector<int>temp;
      while(!q.empty()){
        if(level==0){//这是核心代码，遍历完一层后将下一层数量转移给level，levelnum重新计数
            res.push_back(temp);
            temp.clear();
            level=levelnum;
            levelnum=0;
        }
        TreeNode* node=q.front();
        q.pop();
        if(node->left) {
          q.push(node->left);
          levelnum++;
        }
        if(node->right){
             q.push(node->right);
             levelnum++;
        }
         temp.push_back(node->val);
         level--;
      }
      if(level==0) res.push_back(temp);
      return res;
    }

根据前序遍历与中序遍历来确定该二叉树

前序遍历第一个节点是根节点，则中序遍历中对应节点之前的即为左子树，之后的为右子树。 然后递归着来还原这棵树就行。

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int l=preorder.size();
      if(l==0) return NULL;
       return postorder(preorder,0,l-1,inorder,0,l-1);
    }
  TreeNode*  postorder(vector<int>& preorder,int ps,int pe,vector<int>& inorder,int is,int ie){
        TreeNode* p=new TreeNode(preorder[ps]);
        int i=is;
        while(preorder[ps]!=inorder[i])  i++;
        int left=i-is;
        int right=ie-i;
        if(left>0) p->left=postorder(preorder,ps+1,ps+left,inorder,is,i-1);
        if(right>0) p->right=postorder(preorder,ps+left+1,pe,inorder,i+1,ie);
        return p;
    }