中序和后序构造二叉树
给定二叉树的中序遍历和后序遍历序列，请构造出该二叉树并返回根节点。中序遍历的顺序是左子树->根节点 ->右子树；后序遍历的顺序是左子树->右子树->根节点。
输入格式
·一个整数数组 inorder，表示中序遍历的结果
·一个整数数组 postorder，表示后序遍历的结果
输出格式
返回构造出的二叉树的根节点
输入样例
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]
输出样例
[3, 9, 20, null, null, 15, 7]
二叉树结构
3
/ \
9 20
/ \
15 7
题目要求根据中序遍历和后序遍历构造二叉树，这实际上是经典的重建二叉树问题。我们可以利用中序遍历和后序遍历的特性来逐步确定各个子树的根节点、左子树和右子树，从而构建整个树结构。具体方法如下：
-
从后序遍历的最后一个元素开始，这是树的根节点。
-
在中序遍历中找到这个根节点的位置，这样就可以将中序遍历分为左子树和右子树。
-
回到后序遍历中相应地划分出左子树和右子树的部分，递归地构造子树。
-
重复步骤1到3，直到完成树的构建。
java代码
// Definition for a binary tree node.
class TreeNode {
int val; // 节点的值
TreeNode left; // 左子节点
TreeNode right; // 右子节点
// 构造函数，初始化节点值
TreeNode(int x) {
val = x;
}
}
public class Solution {
/**
* 根据中序遍历和后序遍历的数组构造二叉树
*
* @param inorder 中序遍历数组
* @param postorder 后序遍历数组
* @return 构造的二叉树的根节点
*/
public TreeNode buildTree(int[] inorder, int[] postorder) {
// 如果输入数组为 null，或者两者长度不相等，则无法构造树，返回 null
if (inorder == null || postorder == null || inorder.length != postorder.length) {
return null;
}
// 调用辅助方法构建二叉树
return buildTreeHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
/**
* 递归辅助函数，用于构造二叉树
*
* @param inorder 中序遍历数组
* @param inStart 当前中序数组的起始索引
* @param inEnd 当前中序数组的结束索引
* @param postorder 后序遍历数组
* @param postStart 当前后序数组的起始索引
* @param postEnd 当前后序数组的结束索引
* @return 构造的子树的根节点
*/
private TreeNode buildTreeHelper(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
// 递归终止条件：中序或后序数组范围无效时返回 null
if (inStart > inEnd || postStart > postEnd) {
return null;
}
// 从后序数组的最后一个元素获取当前子树的根节点值
int rootVal = postorder[postEnd];
// 创建根节点
TreeNode root = new TreeNode(rootVal);
// 在中序数组中找到根节点的索引，用于划分左右子树
int rootIndex = inStart;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
// 计算左子树的节点数量
int leftSize = rootIndex - inStart;
// 构造左子树，更新中序和后序数组的范围
root.left = buildTreeHelper(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftSize - 1);
// 构造右子树，更新中序和后序数组的范围
root.right = buildTreeHelper(inorder, rootIndex + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);
// 返回当前子树的根节点
return root;
}
}
C++代码
#include <vector>
using namespace std;
// 定义二叉树节点结构
struct TreeNode {
int val; // 节点值
TreeNode *left; // 左子节点指针
TreeNode *right; // 右子节点指针
// 构造函数，用于初始化节点值并将子节点设置为 nullptr
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
/**
* 根据中序遍历和后序遍历的结果构建二叉树
* @param inorder 中序遍历数组
* @param postorder 后序遍历数组
* @return 构造的二叉树的根节点
*/
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// 调用辅助函数递归构造二叉树
return buildTreeHelper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}
private:
/**
* 递归辅助函数，用于分区构建子树
* @param inorder 中序遍历数组
* @param inStart 当前子树中序遍历起始索引
* @param inEnd 当前子树中序遍历结束索引
* @param postorder 后序遍历数组
* @param postStart 当前子树后序遍历起始索引
* @param postEnd 当前子树后序遍历结束索引
* @return 当前子树的根节点
*/
TreeNode* buildTreeHelper(vector<int>& inorder, int inStart, int inEnd, vector<int>& postorder, int postStart, int postEnd) {
// 递归终止条件：当索引范围无效时返回 nullptr
if (inStart > inEnd || postStart > postEnd) {
return nullptr;
}
// 后序遍历的最后一个元素是当前子树的根节点值
int rootVal = postorder[postEnd];
// 创建根节点
TreeNode* root = new TreeNode(rootVal);
// 在中序遍历数组中找到根节点的位置，以划分左右子树
int rootIndex = inStart;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
// 计算左子树的节点数量
int leftSize = rootIndex - inStart;
// 递归构造左子树
root->left = buildTreeHelper(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftSize - 1);
// 递归构造右子树
root->right = buildTreeHelper(inorder, rootIndex + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);
// 返回当前子树的根节点
return root;
}
};
python代码
# 定义二叉树节点类
class TreeNode:
def __init__(self, x):
self.val = x # 节点的值
self.left = None # 左子节点指针
self.right = None # 右子节点指针
class Solution:
"""
根据中序遍历和后序遍历数组构造二叉树
"""
def buildTree(self, inorder: list[int], postorder: list[int]) -> TreeNode:
# 如果输入数组为空或长度不一致，无法构造树，返回 None
if not inorder or not postorder or len(inorder) != len(postorder):
return None
# 调用辅助函数递归构建二叉树
return self.buildTreeHelper(inorder, 0, len(inorder) - 1, postorder, 0, len(postorder) - 1)
def buildTreeHelper(self, inorder, inStart, inEnd, postorder, postStart, postEnd):
"""
递归辅助函数，用于分区构建二叉树
:param inorder: 中序遍历数组
:param inStart: 当前中序遍历数组的起始索引
:param inEnd: 当前中序遍历数组的结束索引
:param postorder: 后序遍历数组
:param postStart: 当前后序遍历数组的起始索引
:param postEnd: 当前后序遍历数组的结束索引
:return: 构造的二叉树的根节点
"""
# 递归终止条件：索引范围无效时返回 None
if inStart > inEnd or postStart > postEnd:
return None
# 后序遍历的最后一个元素是当前子树的根节点值
rootVal = postorder[postEnd]
# 创建根节点
root = TreeNode(rootVal)
# 在中序遍历数组中找到根节点的位置，用于划分左右子树
rootIndex = inStart
for i in range(inStart, inEnd + 1):
if inorder[i] == rootVal:
rootIndex = i
break
# 左子树的节点数量
leftSize = rootIndex - inStart
# 递归构造左子树
root.left = self.buildTreeHelper(
inorder, inStart, rootIndex - 1,
postorder, postStart, postStart + leftSize - 1
)
# 递归构造右子树
root.right = self.buildTreeHelper(
inorder, rootIndex + 1, inEnd,
postorder, postStart + leftSize, postEnd - 1
)
# 返回当前子树的根节点
return root