『 C++ 』二叉树进阶OJ题（下）

class Solution {
public:
         TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder,int& cur,int inbegin,int inend){
         if(inbegin>inend) return nullptr;
         TreeNode* newnode = new TreeNode(postorder[cur]);
         int mid = inbegin;
         while(mid<=inend){ 
            if(inorder[mid] == postorder[cur]) break;    
            ++mid;
         }
         --cur;
         newnode->right = _buildTree(inorder,postorder,cur,mid+1,inend);
         newnode->left = _buildTree(inorder,postorder,cur,inbegin,mid-1);
         return newnode;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int cur = postorder.size() - 1;
        return _buildTree(inorder, postorder, cur, 0, inorder.size() - 1);
    }
};

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;//用来存放左路节点
        vector<int> ret;//用来做返回
        TreeNode *cur = root;
        while(!st.empty() || cur){
            while(cur){
            //节点必定存在,要么在栈中要么为cur所在位置
            //故当栈不为空或者cur不为nullptr时将其入队列
            st.push(cur);
            //由于该遍历方式为前序遍历即 (根,左子树,右子树) 故该节点可以直接访问
            ret.push_back(cur->val);
            cur = cur->left;//遍历左路节点
            }
            //每次去访问栈顶元素(左路节点)的右子树
            TreeNode*top = st.top();
            st.pop();
            cur = top->right;
        }
        return ret;
    }
};

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;//作为函数返回
        stack<TreeNode*>st;//用来访问左路节点及节点的右子树
        TreeNode*cur = root;//该指针用来遍历左路节点
        while(cur || !st.empty()){//节点必定存在,要么在当前cur,要么在栈中,否则即为遍历结束
            while(cur){
                st.push(cur);
                //将节点入栈,且在入栈时不能直接进行访问,当该节点的左子树被访问完毕才能访问该节点
                cur = cur->left;
            }
            TreeNode* top = st.top();
            st.pop();
            //这个节点必定是这棵树(子树)的左路节点,根据中序遍历(左子树 根 右子树)的顺序可以访问该节点
            ret.push_back(top->val);
            //访问该左路节点的右子树
            cur = top->right;
        }
        return ret;
    }
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;//用来存放右路节点
        vector<int> ret;//用来作返回
        TreeNode *cur = root;//用于遍历
        while(!st.empty() || cur){
            while(cur){
            //节点必定存在,要么在栈中要么为cur所在位置
            //故当栈不为空或者cur不为nullptr时将其入队列
            st.push(cur);
            //由于该遍历方式为变相的前序遍历 即 (根,右子树,左子树) 故该节点可以直接访问
            ret.push_back(cur->val);
            cur = cur->right;//遍历右路节点
            }
            //每次去访问栈顶元素(右路节点)的左子树
            TreeNode*top = st.top();
            st.pop();
            cur = top->left;
        }
        //得出的结果即为 (根,右子树,左子树),逆置后即为 (左子树,右子树,根)即为后序遍历顺序;
        reverse(ret.begin(),ret.end());
        return ret;
    }
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;//用来存放左路节点
        vector<int> ret;//用来做返回
        TreeNode *cur = root;//遍历左路节点
        TreeNode*prev = nullptr; //用来记录每个被访问的节点
        while(!st.empty() || cur){
            while(cur){
                //遍历左路节点,这里遍历左路节点时只对左路节点进行入栈操作
                //由于是后序遍历所以第一次访问根节点的时候不能进行访问
                st.push(cur);
                cur = cur->left;
            }
            TreeNode*top = st.top();//取出栈顶节点并准备访问栈顶节点的右子树(左子树默认已经访问完毕)
            if(top->right == nullptr || prev == top->right){
                //当右子树为空时为了避免对空指针的非法解引用且没必要再对右子树进行访问
                //由于prev指针记录了每次上一次访问的节点,所以当prev == 该节点的右子树时则表示该节点的右子树已经被访问完毕
                //可以直接访问该节点
                ret.push_back(top->val);
                st.pop();
                prev = top;
            }
            else{
                //表示该节点的右子树未被访问过,需要先访问该节点的右子树
                cur = top->right;
            }
        }
        return ret;//返回结果
    }
};