105. Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

先序遍历时，访问的顺序是[根节点 - 左子节点 - 右子节点]。
中序遍历时，访问的顺序是[左子节点 - 根节点 - 右子节点]。
可以注意到根节点与左子节点的顺序是相反的，因此我们可以利用栈将节点储存起来，当挤出时顺序自然是调转的。

按照先序遍历来创建树，遍历先序数组。同时将指针指向中序遍历的数组的头部。
先创建根节点，并将其放入栈中。分为两种情况讨论。

情况一，处理当前根节点的左子节点，并将其入栈：

当栈顶的节点值与中序遍历当前的节点值不同时，说明当前的根节点仍有左子节点。

先序：[根节点 - 左子节点 - 右子节点]
中序：[左子节点 - 根节点 - 右子节点]

此时将栈顶的节点的左子节点设置为先序数组对应的节点，继续遍历下一个先序数组。

栈内：[根节点 - 左子节点]
先序：[根节点 - 左子节点 - 右子节点]
中序：[左子节点 - 根节点 - 右子节点]

情况二，寻找栈内节点们的右子节点：

当栈顶的节点与中序遍历当前的节点值相同时，说明我们经过了当前根节点的先序遍历中的最后一个左子节点。
当前先序数组指针指向了当前栈内节点一个右子节点。

栈内：[根节点 - 左子节点]
先序：[根节点 - 左子节点 - 右子节点]
中序：[左子节点 - 根节点 - 右子节点]

此时我们开始向右移动中序遍历的指针，寻找先序遍历指针中的节点应该是当前栈内哪一个节点的右子节点。
此时栈内节点的顺序，与中序遍历的左子节点顺序正好相反。当栈顶与中序遍历的指针相等时，挤出栈顶并将中序指针右移，直到两者不相等或栈空。
此时将最后挤出的根节点的右子节点设置为当前先序数组对应的节点，继续遍历下一个先序数组。

当遍历完成后，返回根节点即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int j = 0;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(preorder[0]);
        stack.add(root);
        
        for(int i = 1; i < preorder.length; i++){
            TreeNode curr = new TreeNode(preorder[i]);
            TreeNode prev = stack.peek();
            if(inorder[j] != prev.val){
                prev.left = curr;
                stack.add(curr);
            }
            else{
                while(!stack.isEmpty() && inorder[j] == stack.peek().val){
                    prev = stack.pop();
                    j++;
                }
                prev.right = curr;
                stack.add(curr);
            }
        }
        return root;
    }
}