题目
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
提示:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均无重复元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列
思路
先根据先序遍历结果能拿到根节点，然后在中序遍历结果中寻找根节点的位置，中序遍历中根节点之前的数据都是左子树，根节点右边的数据都是右子树，拿到左子树的数据后在到现需遍历的结果中查看左子树的根节点是谁，然后以此类推，就构建出了整个二叉树
需要参数：
使用hashmap存储中序遍历的值和索引位置，方便在根据前序遍历拿到结果的同时能够定位到中序遍历中根节点的索引（中序遍历中根节点左边的位置就是左树的节点，右边的位置就是右树的索引）
构建节点的时候前序遍历需要的节点开始位置和结束位置，中序遍历的开始位置和结束位置。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| private static class Solution {
HashMap<Integer, Integer> indexMap = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
int length = inorder.length;
for (int i = 0; i < length; i++) {
indexMap.put(inorder[i], i);
}
return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
private TreeNode buildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd) {
if (preorderStart > preorderEnd) {
return null;
}
int rootVal = preorder[preorderStart];
TreeNode root = new TreeNode(rootVal);
if (preorderStart == preorderEnd) {
return root;
} else {
int rootInorderIndex = indexMap.get(rootVal);
TreeNode leftNode = buildTree(preorder, preorderStart + 1, preorderStart + (rootInorderIndex - inorderStart), inorder, inorderStart, inorderEnd - 1);
TreeNode rightNode = buildTree(preorder, preorderStart + (rootInorderIndex - inorderStart) + 1, preorderEnd, inorder, rootInorderIndex + 1, inorderEnd);
root.left = leftNode;
root.right = rightNode;
return root;
}
}
}
|
