二叉树的前中后序遍历

二叉树前中后序遍历

二叉树的前中后序遍历，分别基于递归和迭代实现

1.1 前序遍历

114.二叉树的前序遍历

递归实现：基于系统实现的栈实现，在递归函数中只要当前节点非空，就先访问当前节点，在递归访问左子树和右子树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void Traversal(TreeNode* root,vector<int> &visit){
        if(root!=nullptr){
            visit.push_back(root->val); // 访问根节点
            Traversal(root->left,visit);
            Traversal(root->right,visit);
        }
    }
    vector<int> preorderTraversal(TreeNode* root) {
        // 此处要求的是返回一个访问的序列，那么就不能在该函数中进行递归
        vector<int> visit;
        Traversal(root,visit);
        return visit;
    }
};

基于手动栈的模拟递归实现（迭代实现）：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> visit;
        stack<TreeNode*> s;
        while(root||!s.empty()){
            if(root){
                visit.push_back(root->val);
                s.push(root);
                root=root->left;
            }else{
                root=s.top()->right;
                s.pop();
            }
        }
        return visit;
    }
};

1.2 中序遍历

94.二叉树的中序遍历

递归实现和前序遍历基本相同：

class Solution {
public:
    void Traversal(TreeNode* root,vector<int> &visit){
        if(root){
            Traversal(root->left,visit);
            visit.push_back(root->val);
            Traversal(root->right,visit);
        }
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> visit;
        Traversal(root,visit);
        return visit;
    }
};

非递归实现：基本思路也是使用手动维护的栈去模拟系统栈。但是在元素的访问是存在区别，前序遍历是在入栈前就访问了，中序遍历根节点的访问需要在左子树完成访问后进行，那么在迭代实现中如何去判断，左子树访问完成呢，当节点开始向右访问右子树时，此时说明左子树访问完成了，那么在访问右子树之前进行根节点的访问即可。

vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> visit;
        while(root||!s.empty()){
            while(root){ // 此处直接采取不断向左的方式进行，减少判断
                s.push(root);
                root=root->left;
            }
            root=s.top(); // 当前子树的左子树访问完成，根节点出栈
            visit.push_back(root->val);// 访问根节点
            s.pop();
            root=root->right;
        }
        return visit;
    }

1.3 后序遍历

145.二叉树的后续遍历

后序遍历的基本思想：根节点非空，先访问左子树，再访问右子树，最后访问根节点。

基于递归的实现：基本思想就和前中序遍历是相同的。

class Solution {
public:
    void Traversal(TreeNode *root,vector<int> &visit){
        if(root){  // 当前节点非空
            Traversal(root->left,visit);
            Traversal(root->right,visit);
            visit.push_back(root->val);
        }
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> visit;
        Traversal(root,visit);
        return visit;
    }
};

迭代实现：一样是基于手动实现的模拟栈进行，但是此处存在一个较为不同的点，就是关于根节点的访问问题，只有当左右子树都完成访问后，才对根节点进行访问，但是要如何判断右子树完成了访问。

使用一个指针对上一次访问的树节点进行记录，在当前节点为空时需要进行两层判断，首先判断栈顶节点是否存在右孩子并且右孩子不是上一次被访问的节点（对一个子树而言，上一次访问了根的右孩子，那么下一次必然是访问根节点），若成立，说明栈顶节点的右子树还没被访问，访问他的右子树。若不成立，说明栈顶节点需要被访问了，访问栈顶节点并记录，出栈后将当前访问的节点置空。（此时是一棵子树完成了访问，那么就需要向上返回了，置空是为了在后续能够继续访问栈顶进行访问的判断和控制）

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> visit;
        TreeNode* pre=nullptr;
        stack<TreeNode*> s;
        while(root||!s.empty()){
            if(root){
                s.push(root);
                root=root->left;
            }else{
                if(s.top()->right&&s.top()->right!=pre){
                    root=s.top()->right;
                }else{
                    visit.push_back(s.top()->val);
                    pre=s.top();
                    s.pop();
                }
            }
        }
        return visit;
    }
};