当前位置： 面试刷题>> 从前序与中序遍历序列构造二叉树(经典算法150题)
### 题目描述
给定一棵树的前序遍历（根节点-左子树-右子树）和中序遍历（左子树-根节点-右子树）序列，要求根据这两个序列构造出相应的二叉树。
**注意**：
- 树中的节点不包含重复的值。
- 前序遍历的第一个元素即为树的根节点。
- 在中序遍历中，根节点左边的元素都属于左子树，右边的元素都属于右子树。
### 示例
假设给定的前序遍历是 `[3,9,20,15,7]`，中序遍历是 `[9,3,15,20,7]`。
根据这两个序列，我们可以构造出如下的二叉树：
```
3
/ \
9 20
/ \
15 7
```
### PHP 代码示例
```php
class TreeNode {
public $val;
public $left;
public $right;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
function buildTree($preorder, $inorder) {
if (empty($preorder) || empty($inorder)) {
return null;
}
$rootVal = $preorder[0];
$root = new TreeNode($rootVal);
$rootIndexInorder = array_search($rootVal, $inorder);
$root->left = buildTree(array_slice($preorder, 1, $rootIndexInorder), array_slice($inorder, 0, $rootIndexInorder));
$root->right = buildTree(array_slice($preorder, $rootIndexInorder + 1), array_slice($inorder, $rootIndexInorder + 1));
return $root;
}
// 使用示例
$preorder = [3, 9, 20, 15, 7];
$inorder = [9, 3, 15, 20, 7];
$root = buildTree($preorder, $inorder);
// 接下来可以对 $root 进行遍历或其他操作来验证结果
```
### Python 代码示例
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
root_index = inorder.index(root_val)
root.left = buildTree(preorder[1:root_index+1], inorder[:root_index])
root.right = buildTree(preorder[root_index+1:], inorder[root_index+1:])
return root
# 使用示例
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
root = buildTree(preorder, inorder)
# 接下来可以对 root 进行遍历或其他操作来验证结果
```
### JavaScript 代码示例
```javascript
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
function buildTree(preorder, inorder) {
if (preorder.length === 0 || inorder.length === 0) {
return null;
}
const rootVal = preorder[0];
const root = new TreeNode(rootVal);
const rootIndex = inorder.indexOf(rootVal);
root.left = buildTree(preorder.slice(1, rootIndex + 1), inorder.slice(0, rootIndex));
root.right = buildTree(preorder.slice(rootIndex + 1), inorder.slice(rootIndex + 1));
return root;
}
// 使用示例
const preorder = [3, 9, 20, 15, 7];
const inorder = [9, 3, 15, 20, 7];
const root = buildTree(preorder, inorder);
// 接下来可以对 root 进行遍历或其他操作来验证结果
```
这些代码示例展示了如何使用递归来根据给定的前序和中序遍历序列构建二叉树。希望这能帮助你更好地理解这个问题，并在面试中表现出色。在“码小课”网站上，你可以找到更多类似的算法问题和解答。