二叉树的各类遍历方法

二叉树的遍历主要有四种：前序、中序、后序、层序。

遍历的实现方式主要是：递归和非递归。
递归遍历的实现非常容易，非递归的实现需要用到栈，难度要高一点。

节点的定义

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}

前序遍历

先访问根节点，再访问左子树，最后访问右子树。

递归版本

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ret;
    preOrder(root, ret);
    return ret;
}
void preorder(TreeNode* p, vector<int> &ret) {
    if(p==NULL) return;
    ret.push_back(p->val);      // 存储根节点
    preorder(p->left, ret);     // 访问左子树
    preorder(p->right, ret);    // 访问右子树
}

非递归版本

需要利用辅助栈来实现：

1. 首先把根节点压入栈中；
2. 此时栈顶元素即为当前根节点，弹出并访问即可；
3. 把当前根节点的右子树和左子树分别入栈，考虑到栈是先进后出，所以必须右子树先入栈，左子树后入栈；
4. 重复 2~3 步骤，直到栈为空。

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ret;
    if (root==NULL) return ret;
    stack<TreeNode*> st;
    st.push(root);
    while(!st.empty()) {
        TreeNode* tp = st.top();    //取出栈顶元素
        st.pop();
        ret.push_back(tp->val);     //先访问根节点
        if(tp->right!=NULL) st.push(tp->right);    //由于栈时先进后出，考虑到访问顺序，先将右子树压栈
        if(tp->left!=NULL) st.push(tp->left);      //将左子树压栈
    }
    return ret;
}

中序遍历

先访问左子树，再访问根节点，最后访问右子树。

递归版本

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ret;
    inorder(root, ret);
    return ret;
}
void inorder(TreeNode* p, vector<int>& ret) {
    if(p==NULL) return;
    inorder(p->left, ret);     // 访问左子树
    ret.push_back(p->val);     // 访问根节点
    inorder(p->right, ret);    // 访问右子树
}

非递归版本

中序遍历的非递归版本比前序稍微复杂一点，除了用到辅助栈之外，还需要一个指针 p 指向下一个待访问的节点：

• 如果 p 非空，则将 p 入栈，p 指向 p 的左子树；
• 如果 p 为空，说明此时左子树已经访问到尽头了，弹出当前栈顶元素，进行访问，并把 p 设置成 p 的右子树的左子树，即下一个待访问的节点。

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ret;
    TreeNode* p = root;
    stack<TreeNode*> st;
    while(!st.empty() || p!=NULL){
        if(p) {    // p 非空，代表还有左子树，继续
            st.push(p);
            p=p->left;
        }
        else {    // 如果为空，代表左子树已经走到尽头了
            p = st.top();
            st.pop();
            ret.push_back(p->val);     // 访问栈顶元素
            if(p->right) {
                st.push(p->right);     // 如果存在右子树，将右子树入栈
                p = p->right->left;    // p 始终为下一个待访问的节点
            }
            else p=NULL;
        }
    }
    return ret;
}

后序遍历

先访问左子树，再访问右子树，最后访问根节点。

递归版本

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

非递归版本

采用一个辅助栈和两个指针 p 和 r，p 代表下一个需要访问的节点，r 代表上一次需要访问的节点：

1. 如果 p 非空，则将 p 入栈，p 指向 p 的左子树；
2. 如果 p 为空，代表左子树到了尽头，此时判断栈顶元素：
   2.1 如果栈顶元素存在右子树且没有被访问过（等于 r 代表被访问过），则右子树入栈，p 指向右子树的左子树；
   2.2 如果栈顶元素不存在或者已经被访问过，则弹出栈顶元素，访问，然后 p 置为 NULL，r 记录上一次访问的节点 p。

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ret;
    TreeNode* p = root;
    stack<TreeNode*> st;
    TreeNode* r = NULL;
    while(p || !st.empty()) {
        if(p) {
            st.push(p);
            p = p->left;
        }
        else {
            p = st.top();
            if(p->right && p->right!=r) {
                p = p->right;
                st.push(p);
                p = p->left;
            }
            else {
                p = st.top();
                st.pop();
                ret.push_back(p->val);
                r = p;
                p = NULL;
            }
        }
    }
    return ret;
}

层序遍历

每一层从左到右访问每一个节点。
层序遍历需要借助队列 queue 来完成，因为要满足先进先去的访问顺序。

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ret;
    if(root==NULL) return ret;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()) {
        vector<int> temp;
        queue<TreeNode*> tmpQue;    // 存储下一层需要访问的节点
        while(!q.empty()) {    // 从左到右依次访问本层
            TreeNode* tempNode = q.front();
            q.pop();
            temp.push_back(tempNode->val);
            if(tempNode->left!=NULL) tmpQue.push(tempNode->left);      // 左子树压入队列
            if(tempNode->right!=NULL) tmpQue.push(tempNode->right);    // 右子树压入队列
        }
        ret.push_back(temp);
        q = tmpQue;    // 访问下一层
    }
    return ret;
}