【LeetCode】【树】106. 根据中序和后序遍历重建二叉树
5星
- 浏览量: 0
- 大小:None
- 文件类型：PDF
简介：
本题详解如何通过给定的中序和后序遍历结果重建一棵二叉树。讲解了二叉树的基础知识及递归构建方法，适合LeetCode初学者练习。
根据一棵树的中序遍历与后序遍历构造二叉树。
你可以假设树中没有重复的元素。
例如：
给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
9 20
15 7
**解题思路**
**前序中序还原**
前序遍历的第一个元素总是二叉树的根节点，而中序遍历将树分成左子树和右子树两部分。因此，我们可以首先找到中序遍历中的根节点，然后通过这个根节点将两个序列分割成左右两部分。接着，分别对左右两部分递归地执行相同的操作。
**中序后序还原**
后序遍历的最后一个元素是整棵树的根节点。因此，我们可以先找到中序遍历中的根节点，在后续遍历中定位该位置，并将其分为左右两部分。这样可以分别对左右两部分递归构建子树。
**代码实现**
以下是一个Java示例代码，使用了上述方法来解决这个问题：
```java
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public static TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || postorder == null) {
return null;
}
return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
private static TreeNode buildTree(int[] inorder, int iStart, int iEnd, int[] postorder, int pStart, int pEnd) {
if (iStart > iEnd || pStart > pEnd) {
return null;
}
TreeNode treeNode = new TreeNode(postorder[pEnd]);
// 后序遍历的最后一个元素是根节点
int length = 0;
while (inorder[length + iStart] != postorder[pEnd]) {
// 找到根节点在中序遍历中的位置
length++;
}
treeNode.left = buildTree(inorder, iStart, iStart + length - 1, postorder, pStart, pStart + length - 1);
treeNode.right = buildTree(inorder, iStart + length + 1, iEnd, postorder, pStart + length, pEnd - 1);
return treeNode;
}
```
这个算法的时间复杂度是O(n)，因为每个节点都被处理一次；空间复杂度也是O(n)，考虑到递归调用的栈空间。
**总结**
这道题目考察的是对二叉树遍历的理解和递归的应用。通过中序和后序遍历的特点，我们可以有效地构建出一棵二叉树。理解这些基本的二叉树操作对于解决其他更复杂的二叉树问题至关重要。在实际编程中，这类问题常用于面试和技术挑战，掌握这些技巧将有助于提升你在数据结构和算法领域的技能。
全部评论 (0)
