# 从前序与中序遍历序列构造二叉树

<p>给定一棵树的前序遍历 <code>preorder</code> 与中序遍历  <code>inorder</code>。请构造二叉树并返回其根节点。</p>

<p> </p>

<p><strong>示例 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/19/tree.jpg" />
<pre>
<strong>Input:</strong> preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
<strong>Output:</strong> [3,9,20,null,null,15,7]
</pre>

<p><strong>示例 2:</strong></p>

<pre>
<strong>Input:</strong> preorder = [-1], inorder = [-1]
<strong>Output:</strong> [-1]
</pre>

<p> </p>

<p><strong>提示:</strong></p>

<ul>
	<li><code>1 <= preorder.length <= 3000</code></li>
	<li><code>inorder.length == preorder.length</code></li>
	<li><code>-3000 <= preorder[i], inorder[i] <= 3000</code></li>
	<li><code>preorder</code> 和 <code>inorder</code> 均无重复元素</li>
	<li><code>inorder</code> 均出现在 <code>preorder</code></li>
	<li><code>preorder</code> 保证为二叉树的前序遍历序列</li>
	<li><code>inorder</code> 保证为二叉树的中序遍历序列</li>
</ul>


## template

```java
public class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}

public class Solution {
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		if (preorder.length != inorder.length)
			return null;
		if (preorder.length == 0)
			return null;
		if (preorder.length == 1)
			return new TreeNode(preorder[0]);
		return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
	}

	private TreeNode buildTree(int[] preorder, int[] inorder, int prei, int prej, int ini, int inj) {
		if (prei > prej || ini > inj || prei < 0 || prej >= preorder.length || ini < 0 || inj >= inorder.length)
			return null;
		if (prej - prei < 0)
			return null;
		if (prei == prej)
			return new TreeNode(preorder[prei]);
		TreeNode root = new TreeNode(preorder[prei]);
		int inFlag = 0;
		for (int i = ini; i <= inj; i++) {
			if (inorder[i] == root.val) {
				inFlag = i;
				break;
			}
		}
		int num_left = inFlag - ini;
		int num_right = inj - inFlag;
		root.left = buildTree(preorder, inorder, prei + 1, prei + num_left, ini, inFlag - 1);
		root.right = buildTree(preorder, inorder, prej - num_right + 1, prej, inFlag + 1, inj);

		return root;

	}
}


```

## 答案

```java

```

## 选项

### A

```java

```

### B

```java

```

### C

```java

```