输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如,给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3 / \ 9 20 / \ 15 7
限制:
0 <= 节点个数 <= 5000
题解:
递归方式 先根据先序遍历确认根节点,然后找出根节点在中序遍历的位置,从而确定左子树的长度和右子树的长度,对应到先序遍历中也能找出对应的左子树和右子树, 分别递归左子树和右子树,重复上面步骤。
例如:
上面示例所示:
第一次递归:
由先序遍历知:3为根节点,
由中序遍历知,左子树有1个,为9;右子树有3个,为15,20,7
第二次递归:
左子树递归:
先序遍历中,左子树为9,由此,根节点为9
因为中序遍历中9也是根节点。
由此,确认9为跟节点。
右子树遍历:
先序遍历中,右子树为20,15,7,由此,20为根节点。
中序遍历中,则找到20的根节点,则左子树为15,右子树为7.
代码:
public class offer07 {
private static Map<Integer,Integer> indexMap;
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] preorder = new int[]{3,9,20,15,7};
int[] inorder = new int[]{9,3,15,20,7};
TreeNode tree = buildTree(preorder,inorder);
System.out.println(tree);
}
/**
* 思路:主要是递归的定位到根节点
* @param preorder
* @param inorder
* @return
*/
public static TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
//构造哈希映射,帮助我们快速定位根节点
indexMap = new HashMap<Integer,Integer>();
for(int i=0;i<n;i++){
indexMap.put(inorder[i], i);
}
return myBuildTree(preorder,inorder,0,n-1,0,n-1);
}
/**
* 递归方式
* 先根据先序遍历确认根节点,然后找出根节点在中序遍历的位置,从而确定左子树的长度和右子树的长度,对应到先序遍历中也能找出对应的左子树和右子树,
* 分别递归左子树和右子树,重复上面步骤。
*
* @param preorder
* @param inorder
* @param preorder_left
* @param preorder_right
* @param inorder_left
* @param inorder_right
* @return
*/
public static TreeNode myBuildTree(int[] preorder,int[] inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right){
if(preorder_left>preorder_right){
return null;
}
//前序遍历中的第一个节点就是根节点
int preorder_root = preorder_left;
//在中序遍历中定位根节点
int inorder_root = indexMap.get(preorder[preorder_root]);
//先把根节点建立出来
TreeNode root = new TreeNode(preorder[preorder_root]);
//得到左子树中的节点数目
int size_left_subtree = inorder_root - inorder_left;
//递归的构造左子树,并连接到根节点
//先序遍历中【从左边界+1 开始的size_left_subtree】个元素就对应了中序遍历中【从左边界开始到根节点定位-1】的元素
root.left = myBuildTree(preorder,inorder,preorder_left+1,preorder_left+size_left_subtree,inorder_left,inorder_root-1);
//递归的构造右子树,并连接到根节点
//先序遍历中【 从左边界+1 + 左子树节点数目 对应 开始 到右边界】的元素对应了中序遍历中 【从左边界开始 到 根节点-1】的元素
root.right = myBuildTree(preorder,inorder,preorder_left+size_left_subtree+1,preorder_right,inorder_root+1,inorder_right);
return root;
}
}
class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){
val = x;
}
}