剑指offer_【4】重建二叉树

1. 题目描述

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

2.解题思路

1. 先序遍历为：根->左子树->右子树，中序遍历为左子树->根->右子树

2. 先找到根结点，为先序遍历的第一个数值

3. 根据这个数值，可以划分中序中的左子树和右子树范围

4. 递归构建左子树和右子树

3.代码

import java.util.Arrays;
//** * Definition for binary tree 
 public class TreeNode { 
     int val; 
     TreeNode left; 
     TreeNode right; 
     TreeNode(int x) { val = x; } 
 } 
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<pre.length;i++){      
        //找到根节点在中序遍历的点，左边为根的左节点，右边为根的右节点         
            if(pre[0] == in[i]){    
        //递归构建左子树，此时前序的范围缩小为[1,i+1),中序缩小为[0,i)              
             node.left =reConstructBinaryTree(Arrays.copyOfRange
                         (pre,1,i+1),Arrays.copyOfRange(in,0,i));
        //递归构建右子树,此时前序的范围缩小为[i+1,len),中序缩小为[i+1,len)                   
             node.right = reConstructBinaryTree(Arrays.copyOfRange
        (pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));                   
                break;               
            }           
        }           
        return node;
    }
}