题目描述:
输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
解法:
递归
前序遍历:左-根-右 可得 前序遍历数组的第一个元素即为根元素
在中序遍历数组中找到根元素的位置 从该位置分为左右两个数组 分别为左子树和右子树
然后在左子树和右子树 继续递归构造树