剑指offer重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路分析

    这种题型是比较经典的二叉树问题了。做这种题之前一定要熟悉前序遍历，中序遍历，然后还要理解递归思想并且具备把递归思想转化成代码的能力。前序遍历有一个性质，就是遍历结果的第一个元素是根结点，而中序遍历也有一个性质，就是遍历结果中根结点所在位置的左边全是根结点左子树的元素，右边全是根结点右子树的元素。这两个性质可以结合起来利用。题目中给了前序遍历序列 {1,2,4,7,3,5,6,8}，我们由前序遍历的性质可知第一个元素 1 就是该二叉树的根结点，又结合中序遍历的性质可知在中序遍历序列{4,7,2,1,5,3,8,6} 中元素 1 左边的 4,7,2 全是根结点左边的元素，5,3,8,6 全是根结点右边的元素。现在我们可以得到二叉树的基础机构如下：

目前只知道 4,7,2 这三个元素在根节点 1 的左边，5,3,8,6 这四个元素在根节点 1 的右边。
由于二叉树的每个子树也都具备上述的性质，接下来，继续把 4,7,2 当做一个独立的二叉树 L1，重复上面的步骤：先找 4,7,2 中谁是 L1 的“
根节点”，从前序遍历序列中可知 4,7,2 这三个元素最先遍历的是 2，因此 2 是 L1 的“根结点“”，再结合 L1 的中序遍历序列 {4,7,2} 可知 4,7 这两个元素都在 2 的左边。
同理分析 5,3,8,6 这几个元素，把这几个元素当成一个独立二叉树 R1。由前序遍历序列可知 3 是 R1 的根结点，再结合中序遍历序列可知，元素 5 在 3 的左边，元素 8,6 在 3 的右边。现在我们可以得到更清晰的二叉树结构：

对于尚不清晰的子二叉树结构，重复上面步骤即可。

代码

public class Solution {public TreeNode reConstructBinaryTree(int [] pre,int [] in) {if(pre.length == 0||in.length == 0){return null;}
        TreeNode node = new TreeNode(pre[0]);
        for(int i = 0; i < in.length; i++){if(pre[0] == in[i]){// 找到中序遍历序列中，根结点所在位置，以便分割出左子树和右子树做递归操作
                node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
                node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1,in.length));    ·
            }
        }
        return node;
    }
}