当前位置： 面试刷题>> 从中序与后序遍历序列构造二叉树(经典算法150题)
### 题目描述
给定一棵二叉树的中序遍历（inorder）和后序遍历（postorder）序列，要求根据这两个序列重建出原始的二叉树。注意，在二叉树中，每个节点的值都是唯一的。
**示例输入**：
- 中序遍历：`[9, 3, 15, 20, 7]`
- 后序遍历：`[9, 15, 7, 20, 3]`
**示例输出**：
重建的二叉树结构如下（这里不直接展示图形，而是通过节点值描述）：
```
3
/ \
9 20
/ \
15 7
```
### 解题思路
1. **后序遍历的最后一个元素** 总是当前子树的根节点。
2. 在**中序遍历**中找到根节点的位置，这个位置将中序遍历分为左子树和右子树的中序遍历。
3. 根据中序遍历中左子树和右子树的节点数，可以切分出后序遍历中的左子树和右子树。
4. 递归地对左子树和右子树进行中序和后序遍历的重建。
### 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($inorder, $postorder) {
if (empty($inorder) || empty($postorder)) {
return null;
}
$rootVal = end($postorder);
$root = new TreeNode($rootVal);
$rootIndex = array_search($rootVal, $inorder);
$leftInorder = array_slice($inorder, 0, $rootIndex);
$rightInorder = array_slice($inorder, $rootIndex + 1);
$leftPostorder = array_slice($postorder, 0, count($leftInorder));
$rightPostorder = array_slice($postorder, count($leftInorder), -1);
$root->left = buildTree($leftInorder, $leftPostorder);
$root->right = buildTree($rightInorder, $rightPostorder);
return $root;
}
// 示例用法
$inorder = [9, 3, 15, 20, 7];
$postorder = [9, 15, 7, 20, 3];
$root = buildTree($inorder, $postorder);
// 这里假设有打印树或验证树结构的代码
```
### Python 示例代码
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(inorder, postorder):
if not inorder or not postorder:
return None
root_val = postorder[-1]
root = TreeNode(root_val)
root_index = inorder.index(root_val)
left_inorder = inorder[:root_index]
right_inorder = inorder[root_index + 1:]
left_postorder = postorder[:len(left_inorder)]
right_postorder = postorder[len(left_inorder):-1]
root.left = buildTree(left_inorder, left_postorder)
root.right = buildTree(right_inorder, right_postorder)
return root
# 示例用法
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]
root = buildTree(inorder, postorder)
# 这里假设有打印树或验证树结构的代码
```
### 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(inorder, postorder) {
if (inorder.length === 0 || postorder.length === 0) {
return null;
}
const rootVal = postorder[postorder.length - 1];
const root = new TreeNode(rootVal);
const rootIndex = inorder.indexOf(rootVal);
const leftInorder = inorder.slice(0, rootIndex);
const rightInorder = inorder.slice(rootIndex + 1);
const leftPostorder = postorder.slice(0, leftInorder.length);
const rightPostorder = postorder.slice(leftInorder.length, postorder.length - 1);
root.left = buildTree(leftInorder, leftPostorder);
root.right = buildTree(rightInorder, rightPostorder);
return root;
}
// 示例用法
const inorder = [9, 3, 15, 20, 7];
const postorder = [9, 15, 7, 20, 3];
const root = buildTree(inorder, postorder);
// 这里假设有打印树或验证树结构的代码
```
这些示例展示了如何使用给定的中序和后序遍历来重建二叉树。每个示例都遵循了相同的递归逻辑。