C++ 9ns stack solution


  • 0
    A
    class Solution {
    public:
        TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
            int size(inorder.size());
            if(size == 0) return nullptr;
            TreeNode *temp;
            TreeNode *root;
            stack<TreeNode *> st;
            int i(size-1), j(size-1);
            root = new TreeNode(postorder[j--]); 
            st.push(root); 
            while(true) {
                if(inorder[i]!=st.top()->val) {
                    TreeNode *node = new TreeNode(postorder[j--]);
                    st.top()->right = node;
                    st.push(node);
                } else {
                    temp = st.top();
                    st.pop();
                    if(--i<0) break;
                    if(!st.empty() && inorder[i]==st.top()->val)
                        continue;
                    temp -> left = new TreeNode(postorder[j--]);
                    st.push(temp->left);
                }
            }
            return root;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.