根据前序，中序构造二叉树
1. 题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
2. 示例
例如，给出
前序遍历 preorder = [3,9,20,15,7] 根， 左， 右
中序遍历 inorder = [9,3,15,20,7] 左， 根， 右
返回如下的二叉树：
3. 解题思路
思路：前序的第一个元素是根结点的值，在中序中找到该值，中序中该值的左边的元素是根结点的左子树，右边是右子树，然后递归的处理左边和右边
具体来说，前序遍历的第一个值一定为根节点，对应于中序遍历中间的一个点。在中序遍历序列中，这个点左侧的均为根的左子树，这个点右侧的均为根的右子树。这时可以利用递归，分别取前序遍历[1:i+1]和中序遍历的[:i]对应与左子树继续上一个过程，取前序遍历[i+1:]和中序遍历[i+1]对应于右子树继续上一个过程，最终得以重建二叉树。
Python处理会比较简单一些
4. Java实现
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.Arrays;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] tin) {
if (pre.length == 0 || tin.length == 0){
return null;
}
TreeNode root = new TreeNode(pre[0]);
// 找到 第一个元素在 tin 中的位置
int i = getIndex(tin, pre[0]);
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(tin, 0, i));
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(tin, i+1, tin.length));
return root;
}
private int getIndex(int[] array, int value){
int index = 0;
for (int i = 0; i < array.length; i++){
if (array[i] == value){
index = i;
break;
}
}
return index;
}
}
5. Python实现
'''
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
'''
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
if not pre or not tin: #只要一个数组为空，则退出函数
return
if set(pre) != set(tin):#如果数组中有重复元素
return
root = TreeNode(pre[0])
i = tin.index(pre[0])
root.left = self.reConstructBinaryTree(pre[1: i+1], tin[: i])
root.right = self.reConstructBinaryTree(pre[i+1: ], tin[i+1: ])
return root
pre = [1, 2, 3, 5, 6, 4]
tin = [5, 3, 6, 2, 4, 1]
test = Solution()
newTree = test.reConstructBinaryTree(pre, tin)
print(newTree)
#中序遍历
def inorder(newTree):
if newTree:
inorder(newTree.left)
print(newTree.val)
inorder(newTree.right)
inorder(newTree)
