题目
解题思路
- 先序遍历:根左右;
- 中序遍历:左根右;
- 从先序遍历中确定根节点,再从中序遍历中判断左右子树的长度范围,从而确定左右子树的根节点。
代码展示
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int size = preorder.length;
Map<Integer,Integer> store = new HashMap<>();
for (int i = 0; i < inorder.length; i++){
store.put(inorder[i],i);
}
return build(preorder, store,0,0,size - 1);
}
private TreeNode build(int[] preorder, Map<Integer,Integer> store, int root,int left,int right){
if(left > right){
return null;
}
TreeNode node = new TreeNode(preorder[root]);
int middle = store.get(preorder[root]);
node.left = build(preorder, store,root + 1, left, middle - 1);
//middle - left是左子树的长度 1表示下一个节点
node.right = build(preorder, store,root + middle - left + 1, middle + 1, right);
return node;
}
}