public TreeNode fromPreInorder3(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;

        Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
        TreeNode root = null;
        TreeNode nowNode = null;
        int i = 0; // index for the preorder array
        int j = 0; // index for the inorder arry
        boolean leftDone = false; //whether the left sub-tree is completed, if yes, the next child should be right.

        root = new TreeNode(preorder[i++]);
        nowNode = root;
        treeNodeStack.push(root);

        while (i < preorder.length) {
            if (treeNodeStack.size() != 0 && treeNodeStack.peek().val == inorder[j]) {
                j++;
                leftDone = true;
                nowNode = treeNodeStack.pop();
            } else {
                if (!leftDone) {
                    nowNode.left = new TreeNode(preorder[i++]);
                    nowNode = nowNode.left;
                    treeNodeStack.push(nowNode);
                } else {
                    nowNode.right = new TreeNode(preorder[i++]);
                    nowNode = nowNode.right;
                    treeNodeStack.push(nowNode);
                    leftDone = false; // the left sub-tree is not completed for this node
                }
            }
        }

        return root;
    }