已知前序遍历和中序遍历求二叉树
在二叉树中，前序遍历和中序遍历是常用的两种遍历方式。前序遍历是指先访问根节点，然后按照左子树、右子树的顺序访问节点。中序遍历是指先访问左子树，然后访问根节点，最后访问右子树。如果给定一棵二叉树的前序遍历和中序遍历，我们如何构建这棵二叉树呢？
方法一：递归构造
递归构造是一个比较简单的方法。我们先看如何构建一棵二叉树。在前序遍历序列中，第一个数字是根节点的值。在中序遍历序列中，根节点在序列的中间，左子树的节点在根节点左边，右子树的节点在根节点右边。根据这个规律，我们可以递归构造整棵树。具体实现方法如下：
（1）如果前序遍历序列和中序遍历序列都为空，那么树为空。
（2）在前序遍历序列中，第一个数字是根节点的值。在中序遍历序列中找到根节点，它左边的所有数字是左子树的中序遍历序列，右边的所有数字是右子树的中序遍历序列。
（3）利用左子树的中序遍历序列的长度，在前序遍历序列中分割出左子树和右子树的前序遍历序列。
（4）递归构造左子树和右子树。
Java代码示例：
```
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeHelper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd) {
return null;
}
int rootValue = preorder[preStart];
int rootIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootValue) {
rootIndex = i;
break;
}
}
int leftSize = rootIndex - inStart;
TreeNode root = new TreeNode(rootValue);
root.left = buildTreeHelper(preorder, inorder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
root.right = buildTreeHelper(preorder, inorder, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);
return root;
}
```
方法二：迭代实现
上面是递归实现，我们还可以迭代实现。具体步骤如下：
（1）创建一个根节点，将前序遍历的第一个节点作为根节点。
（2）创建一个栈，将根节点压入栈中。
（3）遍历前序遍历序列，从第二个节点开始：
a.如果当前节点的值不等于栈顶节点的值，将当前节点作为栈顶节点的左子节点。
b.如果当前节点的值等于栈顶节点的值，说明当前节点不是栈顶节点的左子节点，需要将栈顶节点弹出。
c.将当前节点压入栈中。
（4）返回根节点。
Java代码示例：
```
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) {
return null;
}
TreeNode root = new TreeNode(preorder[0]);
Stack
stack.push(root);
int inIndex = 0;
for (int i = 1; i < preorder.length; i++) {
TreeNode node = stack.peek();
if (node.val != inorder[inIndex]) {
node.left = new TreeNode(preorder[i]);
stack.push(node.left);
} else {
while (!stack.isEmpty() && stack.peek().val == inorder[inIndex]) {
node = stack.pop();
inIndex++;
}
node.right = new TreeNode(preorder[i]);
stack.push(node.right);
}
}
return root;
}
```
