105. 从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/
9 20
/
15 7
解题思路
基于前序遍历和中序遍历的特点, 分别找到子树的范围, 然后递归处理。
前缀遍历的第一个节点就是根节点。
依据此根节点找到中序遍历此节点的位置.中序遍历此位置左边是其左子树, 右边是其右子树。
依据左子树和右子树的节点的数量, 可以在前序遍历数组找到其左子树和右子树的前序遍历序列。
递归此过程即可。
由于需要遍历中序序列找根节点, 时间复杂度较高。所以可以使用一个HashMap存储每个节点的位置。
private final Map<Integer, Integer> map = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
public TreeNode buildTree(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
if (inStart > inEnd) {
return null;
}
int rootValue = preorder[preStart];
int rootIndex = map.get(rootValue);
TreeNode rootNode = new TreeNode(rootValue);
// 将中序数组分为左右子树
rootNode.left = buildTree(preorder, preStart + 1, preStart + (rootIndex - inStart),
inorder, inStart, rootIndex - 1);
rootNode.right = buildTree(preorder, preStart + (rootIndex - inStart) + 1, preEnd,
inorder, rootIndex + 1, inEnd);
return rootNode;
}