重建二叉树
问题描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字
解题思路
递归法
- 先使用字典保存
前序遍历数组中每个元素在中序遍历数组中对应的索引值，目的：空间换时间。大体思路：对于每个前序遍历数组中的元素X，查字典得其对应得索引值I，则其左子树的所有值在中序遍历数组中索引值为I的左边，右子树的所有元素在中序遍历数组中索引值为I的右边，递归建树即可 - 时间复杂度：
O(n)，空间复杂度：O(n)
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0)
return null;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; ++i) {
map.put(inorder[i], i);
}
return helper(0, preorder, map, 0, preorder.length - 1);
}
// i: 先序遍历的索引
// left: 以 preorder[i] 为根的树，其左子树在中序遍历数组中开始的位置
// right: 以 preorder[i] 为根的树，其右子树在中序遍历数组中结束的位置
private TreeNode helper(int i, int[] preorder, Map<Integer, Integer> map, int left, int right) {
if (left > right)
return null;
TreeNode cur = new TreeNode(preorder[i]);
int idx = map.get(preorder[i]);
cur.left = helper(i + 1, preorder, map, left, idx - 1);
// idx - left 表示以 cur 为根，其左子树的节点个数
cur.right = helper(i + idx - left + 1, preorder, map, idx + 1, right);
return cur;
}
}
