二叉树的先序中序后序访问

二叉树的先序/后序/中序 的递归访问

class SolutionA{
    vector<int> result;//保存访问的值
    void preTraversal(TreeNode* root){//先序访问
        if (root == nullptr) {
            return;
        }
        result.push_back(root->val);
        preTraversal(root->left);
        preTraversal(root->right);
    }
    void middleTraversal(TreeNode* root){//中序访问
        if (root == nullptr) {
            return;
        }
        middleTraversal(root->left);
        result.push_back(root->val);
        middleTraversal(root->right);
    }

    void afterTraversal(TreeNode* root){//后序访问
        if (root == nullptr) {
            return;
        }
        afterTraversal(root->left);
        afterTraversal(root->right);
        result.push_back(root->val);

    }
};

二叉树的先序/后序/中序 的迭代访问 （向递归一样完美）

class SolutionB{
    vector<int> result;//保存访问的值
    stack<TreeNode*>stk;
    void preTraversal(TreeNode* root){//先序访问
        if (root ==nullptr) {
            return;
        }
        stk.push(root);
        while (stk.size() >0) {
            TreeNode *temp = stk.top();
            if (temp != nullptr) {
                stk.pop();
                if (temp->right) {
                    stk.push(temp->right);
                }
                if (temp->left) {
                    stk.push(temp->left);
                }
                stk.push(temp);
                stk.push(nullptr);
            }
            else{
                stk.pop();//弹走 null
                temp = stk.top();
                stk.pop();
                result.push_back(temp->val);
            }
        }
    }
    void middleTraversal(TreeNode* root){//中序访问
        if (root ==nullptr) {
            return;
        }
        stk.push(root);
        while (stk.size() >0) {
            TreeNode *temp = stk.top();
            if (temp != nullptr) {
                stk.pop();
                if (temp->right) {
                    stk.push(temp->right);
                }
                stk.push(temp);
                stk.push(nullptr);

                if (temp->left) {
                    stk.push(temp->left);
                }
            }
            else{
                stk.pop();//弹走 null
                temp = stk.top();
                stk.pop();
                result.push_back(temp->val);
            }
        }
    }

    void afterTraversal(TreeNode* root){//后序访问
        if (root ==nullptr) {
            return;
        }
        stk.push(root);
        while (stk.size() >0) {
            TreeNode *temp = stk.top();
            if (temp != nullptr) {
                stk.push(temp);
                stk.push(nullptr);
                stk.pop();
                if (temp->right) {
                    stk.push(temp->right);
                }
                if (temp->left) {
                    stk.push(temp->left);
                }
            }
            else{
                stk.pop();//弹走 null
                temp = stk.top();
                stk.pop();
                result.push_back(temp->val);
            }
        }

    }
};

参考链接 https://mp.weixin.qq.com/s/WKg0Ty1_3SZkztpHubZPRg