根据前序遍历和[中序遍历]
1. 递归法：
先序遍历：根节点→左子树→右子树。
中序遍历：左子树→根节点→右子树。
后续遍历：左子树→右子树→根节点。
根据前序遍历和中序遍历建立二叉树，根据以上性质可知：
前序遍历首个元素为二叉树的根节点root； 根据前序遍历找到中序遍历中的root的索引位置，可以将中序遍历分为【左子树|根节点|右子树】； 根据中序遍历的左/右子树可以将前序遍历分为【根节点|左子树|右子树】。
递推参数： 根节点在前序遍历的索引 root 、子树在中序遍历的左边界 left 、子树在中序遍历的右边界 right ；
终止条件： 当 left > right ，代表已经越过叶节点，此时返回 null；
递推工作：
建立根节点 node ： 节点值为 preorder[root] ；
划分左右子树： 查找根节点在中序遍历 inorder 中的索引 i ；
为了提升效率，本文使用哈希表 dic 存储中序遍历的值与索引的映射，查找操作的时间复杂度为 O(1)；
构建左右子树： 开启左右子树递归；
| 根节点索引 | 中序遍历左边界 | 中序遍历右边界 | |
| 左子树 | root + 1 | left | i-1 |
| 右子树 | root+i-left+1 | i+1 | right |
i - left + root + 1含义为 根节点索引 + 左子树长度 + 1
返回值： 回溯返回 node ，作为上一层递归中根节点的左 / 右子节点；
代码：
int[] preorder; HashMap<Integer, Integer> dic = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { this.preorder = preorder; for(int i = 0; i < inorder.length; i++) dic.put(inorder[i], i); return recur(0, 0, inorder.length - 1); } TreeNode recur(int root, int left, int right) { if(left > right) return null; // 递归终止 TreeNode node = new TreeNode(preorder[root]); // 建立根节点 int i = dic.get(preorder[root]); // 划分根节点、左子树、右子树 node.left = recur(root + 1, left, i - 1); // 开启左子树递归 node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归 return node; // 回溯返回根节点 } }
