问题描述
LeetCode 105. 从前序与中序遍历序列构造二叉树 (opens in a new tab)，难度中等。
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
示例 2
输入: preorder = [-1], inorder = [-1] 输出: [-1]
提示:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder和inorder均 无重复 元素inorder均出现在preorderpreorder保证 为二叉树的前序遍历序列inorder保证 为二叉树的中序遍历序列
题解
Solution.java
class Solution {
int[] preorder;
int[] inorder;
HashMap<Integer, Integer> map = new HashMap<>();
int preIndex;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
this.inorder = inorder;
preIndex = 0;
for (int i = 0; i < inorder.length; ++i) {
map.put(inorder[i], i);
}
return buildTreeHelper(0, preorder.length - 1);
}
public TreeNode buildTreeHelper(int left, int right) {
if (left > right) return null;
TreeNode root = new TreeNode(preorder[preIndex]);
int index = map.get(preorder[preIndex]);
preIndex++;
root.left = buildTreeHelper(left, index - 1);
root.right = buildTreeHelper(index + 1, right);
return root;
}
}