94-144-145二叉树三序遍历

所谓三序遍历，就是前序遍历，中序遍历和后序遍历。那么在之前的博客二叉树当中我已经详细的写了二叉树的基本知识，构建，遍历。在leetcode上，也有这三道题目。

题目给出的代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        
    }
};

所以这三道题目，不仅仅要利用递归的思路解出来（简单),还要用迭代+栈的做法解。

递归法求解

先序遍历

class Solution {
public:
    vector<int> results;
    vector<int> preorderTraversal(TreeNode* root) {
        traverse(root);
        return results;
    }

    void traverse(TreeNode* node){
        if(node==NULL) return;
        results.push_back(node->val);
        traverse(node->left);
        traverse(node->right);
    }
};

中序遍历

class Solution {
public:
    vector<int> results;
    vector<int> inorderTraversal(TreeNode* root) {
        traverse(root);
        return results;
    }

    void traverse(TreeNode* node){
        if(node==NULL) return;
        traverse(node->left);
        results.push_back(node->val);
        traverse(node->right);
    }
};

后序遍历

class Solution {
public:
    vector<int> results;
    vector<int> postorderTraversal(TreeNode* root) {
        traverse(root);
        return results;
    }

    void traverse(TreeNode* node){
        if(node==NULL) return;
        traverse(node->left);
        traverse(node->right);
        results.push_back(node->val);
    }
};

迭代法求解

迭代法求解我主要学习了leetcode 优秀题解 。我认为他的方法最简明扼要。

先序遍历

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;  //保存结果
        stack<TreeNode*> call;  //调用栈
        if(root!=nullptr) call.push(root);  //首先压入root节点
        while(!call.empty()){
            TreeNode *t = call.top();
            call.pop();  //访问过的节点弹出
            if(t!=nullptr){
                if(t->right) call.push(t->right);  //右节点先压栈，最后处理
                if(t->left) call.push(t->left);
                call.push(t);  //当前节点重新压栈（留着以后处理），因为先序遍历所以最后压栈
                call.push(nullptr);  //在当前节点之前加入一个空节点表示已经访问过了
            }else{  //空节点表示之前已经访问过了，现在需要处理除了递归之外的内容
                res.push_back(call.top()->val);  
                //call.top()是nullptr之前压栈的一个节点，也就是上面call.push(t)中的那个t
                call.pop();  //处理完了，第二次弹出节点（彻底从栈中移除）
            }
        }
        return res;
    }
};

中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;  //保存结果
        stack<TreeNode*> call;  //调用栈
        if(root!=nullptr) call.push(root);  //首先压入root节点
        while(!call.empty()){
            TreeNode *t = call.top();
            call.pop();  //访问过的节点弹出
            if(t!=nullptr){
                if(t->right) call.push(t->right);  //右节点先压栈，最后处理
                call.push(t);  
                //当前节点重新压栈（留着以后处理），因为中序遍历所以根节点摆中间
                call.push(nullptr);  //在当前节点之前加入一个空节点表示已经访问过了
                if(t->left) call.push(t->left); //左节点最后压栈，最先处理
            }else{  //空节点表示之前已经访问过了，现在需要处理除了递归之外的内容
                res.push_back(call.top()->val);  
                //call.top()是nullptr之前压栈的一个节点，也就是上面call.push(t)中的那个t
                call.pop();  //处理完了，第二次弹出节点（彻底从栈中移除）
            }
        }
        return res;
    }
};

后序遍历

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;  //保存结果
        stack<TreeNode*> call;  //调用栈
        if(root!=nullptr) call.push(root);  //首先压入root节点
        while(!call.empty()){
            TreeNode *t = call.top();
            call.pop();  //访问过的节点弹出
            if(t!=nullptr){
                call.push(t);  
                //当前节点重新压栈（留着以后处理），因为后序序遍历所以根节点摆最后，最先入栈
                call.push(nullptr);  //在当前节点之前加入一个空节点表示已经访问过了
                if(t->right) call.push(t->right);  //右节点压栈，摆在第二位处理
                if(t->left) call.push(t->left);		//左节点最后入栈，最先处理
            }else{  //空节点表示之前已经访问过了，现在需要处理除了递归之外的内容
                res.push_back(call.top()->val);  
                //call.top()是nullptr之前压栈的一个节点，也就是上面call.push(t)中的那个t
                call.pop();  //处理完了，第二次弹出节点（彻底从栈中移除）
            }
        }
        return res;
    }
};