前序遍歷

對根節(jié)點，左右子樹采取根左右的順序進行遍歷。

遞歸

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;//使用棧來存儲節(jié)點
       auto p=root;
       while(p||!s.empty()){//二者有一個滿足循環(huán)就可以繼續(xù)
            while(p){ //先訪問根節(jié)點，訪問完之后再入棧
                res.push_back(p->val);
                s.push(p);
                p=p->left;
            }
            p=s.top();
            s.pop();
            //彈出棧頂結(jié)點，開始遍歷其右子樹
            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);  //對根節(jié)點的訪問放在其左子樹之后，前序和中序的區(qū)別就在這里。
            p=p->right;
        }
        return res;
    }

后序遍歷

左右根的順序

遞歸

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

非遞歸

后序遍歷比起前兩種又復(fù)雜一點點，因為你在訪問到根節(jié)點的時候無法判斷它的右子樹是否已經(jīng)遍歷完，

  vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> ss;
        auto p=root;
        TreeNode* pre=nullptr;//設(shè)置一個前置指針，指向遍歷的上一個結(jié)點
        while(!ss.empty()||p){
            while(p){
                 ss.push(p);
                p=p->left;
            }
            p=ss.top();
          if(p->right==nullptr||p->right==pre){ //在這里判斷右子樹有沒有遍歷完畢，若已遍歷完，則訪問當(dāng)前節(jié)點。
              res.push_back(p->val);
              ss.pop();
              pre=p;
              p=nullptr;//p指針需要置空，確保循環(huán)可以正確退出
          }
           else  
            p=p->right;
        }
        return res;
    }

層次遍歷

對同一層次的結(jié)點，從左至右依次輸出，使用隊列很方便

一次性遍歷

    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) { //返回一個二維數(shù)組
        vector<vector<int>>res;
                if(!root) return res;
        queue<TreeNode*>q;
        q.push(root);
        int levelnum=0;//下一層結(jié)點的數(shù)目
        int level=1;//當(dāng)前層節(jié)點的數(shù)目
        vector<int>temp;
      while(!q.empty()){
        if(level==0){//這是核心代碼，遍歷完一層后將下一層數(shù)量轉(zhuǎn)移給level，levelnum重新計數(shù)
            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;
    }

根據(jù)前序遍歷與中序遍歷來確定該二叉樹

前序遍歷第一個節(jié)點是根節(jié)點，則中序遍歷中對應(yīng)節(jié)點之前的即為左子樹，之后的為右子樹。 然后遞歸著來還原這棵樹就行。

    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;
    }