题目
给定两个整数数组
preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
解题思路
- 先序遍历：根左右；
- 中序遍历：左根右；
- 从先序遍历中确定根节点，再从中序遍历中判断左右子树的长度范围，从而确定左右子树的根节点。
代码展示
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; } }
