二叉树的遍历方法总结

使用C++实现

二叉树节点结构

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
}

二叉树的先序遍历

递归方法

    vector<int> ans;
    void preorderTraversal(TreeNode* root) {
        if(!root)return;
        ans.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }

非递归方法

1.直观理解的方法（基于中序遍历的非递归方案）

    vector<int> preorderTraversal(TreeNode* root) {
       stack<TreeNode*> tstack;
        vector<int> ans;
        TreeNode* p=root;
        while(p || !tstack.empty()){
            while(p){
                tstack.push(p);
                ans.push_back(p->val);
                p=p->left;
            }
            p=tstack.top();
            tstack.pop();
            p=p->right;
        }
        return ans;
    }

2.更简洁的实现方法

  // 首先访问根节点，然后将右孩子入栈（如果存在），再将左孩子入栈（如果存在）
  // 使左子树始终在右子树之前出栈（栈的特性），从而实现先访问根，再访问左子树，最后访问右子树。
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*>tstack;
        vector<int>ans;
        TreeNode* p=root;
        tstack.push(root);
        while(!tstack.empty()){
            p=tstack.top();
            tstack.pop();
            if(p!=NULL){
                ans.push_back(p->val);
                if(p->right!=NULL)tstack.push(p->right);
                if(p->left!=NULL)tstack.push(p->left); 
            }
        }
        return ans;
    }

二叉树的中序遍历

递归方法

    vector<int> ans;
    void inorderTraversal(TreeNode* root) {
        if(!root)return;
        inorderTraversal(root->left);
        ans.push_back(root->val);
        inorderTraversal(root->right);
    }

非递归方法

与先序遍历直观理解的方法基本一致，只有访问节点的位置不同，先序遍历是第一次遇到节点时（节点入栈时）就访问它，
而中序遍历是第二次遇到时（节点出栈时）再访问它

    vector<int> inorderTraversal(TreeNode* root) {
       stack<TreeNode*> tstack;
        vector<int> ans;
        TreeNode* p=root;
        while(p || !tstack.empty()){
            while(p){
                tstack.push(p);
                p=p->left;
            }

            p=tstack.top();
            tstack.pop();
            ans.push_back(p->val);
            p=p->right;
        }
        return ans;
    }

二叉树的后序遍历

递归方法

    vector<int> ans;
    void postorderTraversal(TreeNode* root) {
        if(!root)return;
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        ans.push_back(root->val);
    }

非递归方法

1.直观的理解方法

// 通过一个辅助指针，记录最近访问过的节点，从而判断访问当前节点的来源是由右子树回退还是左子树回退。
// 如果是左子树回退，则需要继续访问右子树；
// 否则就出栈当前节点，并记录为最近访问的节点，且将标记下一访问的节点位置p置空（否则会再次访问p）。
vector<int> postorderTraversal(TreeNode* root) {
    vector<int>ans;
    stack<TreeNode*>tstack;

    TreeNode*p=root;
    TreeNode*r=NULL;
    while(p || !tstack.empty()){
        while(p){
            tstack.push(p);
            p=p->left;
        }
        p=tstack.top();
        if(p->right && p->right!=r)
            p=p->right;
        else{
            tstack.pop();
            ans.push_back(p->val);
            r=p;
            p=NULL;
        }      
    }
        return ans;
}

2.更简洁的方法

如下列二叉树：

先序遍历为：[1,2,4,5,3,6]

后序遍历为：[4,5,2,6,3,1]

后序遍历的逆序为：[1,3,6,2,5,4]

结合上图来看，后序遍历的逆序就是先访问根节点再访问右子树最后访问左子树的遍历。

这类似于先序遍历，可以按照之前先序遍历的简洁写法，先把左孩子压栈，再把右孩子压栈，

保证右孩子的访问优先级在左孩子之前，就可以得到后序遍历的逆序，最后翻转逆序即可获得后序遍历。

    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*>tstack;
        vector<int>ans;
        TreeNode* p=root;
        tstack.push(root);
        while(!tstack.empty()){
            p=tstack.top();
            tstack.pop();
            if(p!=NULL){
                ans.push_back(p->val);
                if(p->left)tstack.push(p->left);
                if(p->right)tstack.push(p->right); 
            }
        }
        reverse(ans.begin(),ans.end());  // 翻转
        return ans;
    }

二叉树的层次遍历

普通的层次遍历与BFS基本一致，这里稍加改进，对每一层具体是哪些节点做了记录。

    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;  // 节点按层集中存放
        queue<TreeNode*> queue;
        int cnt=0;  // 记录当前层的节点数
        if(root)queue.push(root),cnt++;

        while(cnt || !queue.empty()){
            int maxx=0;  // 记录下一层入队的节点数
            vector<int> tmp;  // 存储一层的节点
            while(cnt){    // 出队当前层的节点
                TreeNode* p=queue.front();
                queue.pop();
                tmp.push_back(p->val);
                cnt--;
                if(p->left){queue.push(p->left);maxx++;}
                if(p->right){queue.push(p->right);maxx++;}
            }
            ans.push_back(tmp);
            cnt=maxx;
        }
        return ans;
    }