1. 题目
剑指 Offer 07. 重建二叉树
2. 描述
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \\
1
2
9 20
/ \
15 7
限制：
0 <= 节点个数 <= 5000
3. 实现方法
3.1 方法 1
3.1.1 思路
利用指针
前序遍历的第一个元素肯定是二叉树的根节点，我么可以查找该节点在中序遍历中的位置，然后拆分出左右子树；
其中用一个指针用于指向根节点所在索引位置，然后根据该指针位置来拆分左右子树；
最后递归求出左右子树即可；
3.1.2 实现
public TreeNode buildTree(int[] preorder, int[] inorder) { return recursive(0, 0, inorder.length - 1, preorder, inorder); } public TreeNode recursive(int preStart, int inStart, int inEnd, int[] preOrder, int[] inOrder){ // if(inStart > inEnd || preStart > preOrder.length - 1){ return null; } // 创建根节点，根节点即为先序遍历中的第一个元素 TreeNode root = new TreeNode(preOrder[preStart]); // 用于存储不同子树的根节点的索引位置 int index = 0; // 在中序遍历中找到根节点 root 的位置，然后拆分出来左右子树 for(int i = inStart; i <= inEnd; i++){ if(root.val == inOrder[i]){ // 此时 root 在中序遍历中的索引位置为 i index = i; break; } } // 递归拆分左右子树 // index-instart+1 就是当前节点左子树的数量加上当前节点的数量 // 所以preStart+(index-instart+1)就是当前节点右子树前序遍历开始的位置 root.left = recursive(preStart + 1, inStart, index - 1, preOrder, inOrder); root.right = recursive(preStart + index - inStart + 1, index + 1, inEnd, preOrder,inOrder); return root; }
