Clean Codes🔥🔥|| Full Explanation✅|| Using Stack✅|| C++|| Java|| Python3
Intuition :\n- Given two integer arrays inorder and postorder ,construct and return the binary tree.\n Describe your first thoughts on how to solve this problem
# Intuition :\n- Given two integer arrays inorder and postorder ,construct and return the binary tree.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach : Iterative Approach using Stack\n- Use the last element in the postorder traversal as the root node, then iterate over the rest of the postorder traversal from right to left. \n- For each element, we create a new node and add it to the stack. We then check if the new node is the left or right child of the previous node. \n- If it\'s the left child, we simply attach it to the previous node. \n- If it\'s the right child, we pop the stack until we find the parent node whose left child is the previous node, and attach the new node to its right child. \n- We repeat this process until we\'ve processed all the nodes in the postorder traversal.\n<!-- Describe your approach to solving the problem. -->\n**Credits to @mayijie88 for helping me out**\n# Let\'s See an Example :\n-  Let\'s take the following inorder and postorder traversals as an example:\n```\ninorder = [9,3,15,20,7]\npostorder = [9,15,7,20,3]\n```\n- So we want to use these traversals to build a binary tree. \n# Steps to be followed :\n- Both the inorder and postorder traversals are non-empty, so we can continue.\n\n```\nip = 4 (the index of the last element in the inorder traversal), \npp = 4 (the index of the last element in the postorder traversal).\n```\n- We create an empty `stack` and initialize `prev` to `null`.\n- We create the root node using the last element in the postorder traversal, which is 3. We push the root node onto the stack and decrement pp to 3.\n\n```\nStack:\n| 3 |\n```\n\n- We iterate over the rest of the postorder traversal from right to left. The next element is 20. \n- We create a new node for 20 and push it onto the stack. We check if 20 is the left or right child of the previous node (which is 3). \n- Since it\'s the right child, we pop the stack until we find the parent node whose left child is 3, which is null. \n- We attach 20 as the right child of 3, and push 20 onto the stack. prev is set to null.\n\n```\nStack:\n| 20 |\n| 3 |\n```\n\n- The next element is 7. We create a new node for 7 and push it onto the stack. We check if 7 is the left or right child of the previous node (which is 20). \n- Since it\'s the right child, we pop the stack until we find the parent node whose left child is 20, which is 3. \n- We attach 7 as the right child of 20, and push 7 onto the stack. prev is set to null.\n\n```\nStack:\n| 7 |\n| 20 |\n| 3 |\n```\n\n- The next element is 15. We create a new node for 15 and push it onto the stack. We check if 15 is the left or right child of the previous node (which is 7). \n- Since it\'s the left child, we attach 15 as the left child of 7, and push 15 onto the stack. prev is set to null.\n\n```\nStack:\n| 15 |\n| 7 |\n| 20 |\n| 3 |\n```\n\n- The next element is 9. We create a new node for 9 and push it onto the stack. We check if 9 is the left or right child of the previous node (which is 15). \n- Since it\'s the left child, we attach 9 as the left child of 15, and push 9 onto the stack. prev is set to null.\n\n```\nStack:\n| 9 |\n| 15 |\n| 7 |\n| 20 |\n| 3 |\n```\n\n- We\'ve processed all the elements in the postorder traversal, so we can return the root node of the binary tree, which is 3.\n- The resulting binary tree looks like this:\n```\n     3\n   /   \\\n  9     20\n       /  \\\n     15    7\n\n```\n# Complexity :\n- Time complexity : O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity : O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution.\uD83D\uDE0A\n```\n# Codes [C++ |Java |Python3] : With Comments\n```Java []\nclass Solution \n{\n    public TreeNode buildTree(int[] inorder, int[] postorder) {\n    // If either of the input arrays are empty, the tree is empty, so return null\n    if (inorder.length == 0 || postorder.length == 0) return null;\n    \n    // Initialize indices to the last elements of the inorder and postorder traversals\n    int ip = inorder.length - 1;\n    int pp = postorder.length - 1;\n\n    // Create an empty stack to help us build the binary tree\n    Stack<TreeNode> stack = new Stack<TreeNode>();\n    // Initialize prev to null since we haven\'t processed any nodes yet\n    TreeNode prev = null;\n    // Create the root node using the last element in the postorder traversal\n    TreeNode root = new TreeNode(postorder[pp]);\n    // Push the root onto the stack and move to the next element in the postorder traversal\n    stack.push(root);\n    pp--;\n\n    // Process the rest of the nodes in the postorder traversal\n    while (pp >= 0) {\n        // While the stack is not empty and the top of the stack is the current inorder element\n        while (!stack.isEmpty() && stack.peek().val == inorder[ip]) {\n            // The top of the stack is the parent of the current node, so pop it off the stack and update prev\n            prev = stack.pop();\n            ip--;\n        }\n        // Create a new node for the current postorder element\n        TreeNode newNode = new TreeNode(postorder[pp]);\n        // If prev is not null, the parent of the current node is prev, so attach the node as the left child of prev\n        if (prev != null) {\n            prev.left = newNode;\n        // If prev is null, the parent of the current node is the current top of the stack, so attach the node as the right child of the current top of the stack\n        } else if (!stack.isEmpty()) {\n            TreeNode currTop = stack.peek();\n            currTop.right = newNode;\n        }\n        // Push the new node onto the stack, reset prev to null, and move to the next element in the postorder traversal\n        stack.push(newNode);\n        prev = null;\n        pp--;\n    }\n\n    // Return the root of the binary tree\n    return root;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {\n    // If either of the input vectors are empty, the tree is empty, so return null\n    if (inorder.size() == 0 || postorder.size() == 0) return nullptr;\n\n    // Initialize indices to the last elements of the inorder and postorder traversals\n    int ip = inorder.size() - 1;\n    int pp = postorder.size() - 1;\n\n    // Create an empty stack to help us build the binary tree\n    stack<TreeNode*> st;\n    // Initialize prev to null since we haven\'t processed any nodes yet\n    TreeNode* prev = nullptr;\n    // Create the root node using the last element in the postorder traversal\n    TreeNode* root = new TreeNode(postorder[pp]);\n    // Push the root onto the stack and move to the next element in the postorder traversal\n    st.push(root);\n    pp--;\n\n    // Process the rest of the nodes in the postorder traversal\n    while (pp >= 0) {\n        // While the stack is not empty and the top of the stack is the current inorder element\n        while (!st.empty() && st.top()->val == inorder[ip]) {\n            // The top of the stack is the parent of the current node, so pop it off the stack and update prev\n            prev = st.top();\n            st.pop();\n            ip--;\n        }\n        // Create a new node for the current postorder element\n        TreeNode* newNode = new TreeNode(postorder[pp]);\n        // If prev is not null, the parent of the current node is prev, so attach the node as the left child of prev\n        if (prev != nullptr) {\n            prev->left = newNode;\n        // If prev is null, the parent of the current node is the current top of the stack, so attach the node as the right child of the current top of the stack\n        } else if (!st.empty()) {\n            TreeNode* currTop = st.top();\n            currTop->right = newNode;\n        }\n        // Push the new node onto the stack, reset prev to null, and move to the next element in the postorder traversal\n        st.push(newNode);\n        prev = nullptr;\n        pp--;\n    }\n\n    // Return the root of the binary tree\n    return root;\n    }\n};\n```\n```Python []\nclass Solution:\n    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n        # If either of the input lists are empty, the tree is empty, so return None\n        if not inorder or not postorder:\n            return None\n\n        # Initialize indices to the last elements of the inorder and postorder traversals\n        ip = len(inorder) - 1\n        pp = len(postorder) - 1\n\n        # Create an empty stack to help us build the binary tree\n        st = []\n        # Initialize prev to None since we haven\'t processed any nodes yet\n        prev = None\n        # Create the root node using the last element in the postorder traversal\n        root = TreeNode(postorder[pp])\n        # Push the root onto the stack and move to the next element in the postorder traversal\n        st.append(root)\n        pp -= 1\n\n        # Process the rest of the nodes in the postorder traversal\n        while pp >= 0:\n            # While the stack is not empty and the top of the stack is the current inorder element\n            while st and st[-1].val == inorder[ip]:\n                # The top of the stack is the parent of the current node, so pop it off the stack and update prev\n                prev = st.pop()\n                ip -= 1\n            # Create a new node for the current postorder element\n            new_node = TreeNode(postorder[pp])\n            # If prev is not None, the parent of the current node is prev, so attach the node as the left child of prev\n            if prev:\n                prev.left = new_node\n            # If prev is None, the parent of the current node is the current top of the stack, so attach the node as the right child of the current top of the stack\n            elif st:\n                curr_top = st[-1]\n                curr_top.right = new_node\n            # Push the new node onto the stack, reset prev to None, and move to the next element in the postorder traversal\n            st.append(new_node)\n            prev = None\n            pp -= 1\n\n        # Return the root of the binary tree\n        return root\n```\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\n![ezgif-3-22a360561c.gif](https://assets.leetcode.com/users/images/87e7df80-afcb-49bb-a54c-5298664e2f43_1678932835.5335186.gif)\n
['Stack', 'Python', 'C++', 'Java', 'Python3']