博客

描述
给定节点数为 n 二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

提示:
1.vin.length == pre.length
2.pre 和 vin 均无重复元素
3.vin出现的元素均出现在 pre里
4.只需要返回根结点，系统会自动输出整颗树做答案对比
数据范围：，节点的值
要求：空间复杂度O(n) ，时间复杂度O(n)

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if(pre==null || vin==null || pre.length!=vin.length || pre.length<1){
            return null;
        }
        TreeNode root = sub(pre, vin, 0, pre.length-1, 0, vin.length-1);
        
        return root;
        
    }
    
    public TreeNode sub(int[] pre, int[] vin, int left, int right, int low, int high){
        // 确定终止条件
        if(left>right || low>high){
            return null;
        }
        // 找到当前子树的根节点
        TreeNode root = new TreeNode(pre[left]);
        // 找到中序遍历里的根节点位置，左侧为左子树，右侧为右子树
        int mid = -1;
        for(int i=low;i<=high;i++){
            if(pre[left]==vin[i]){
                mid=i;
                break;
            }
        }
        int left_num = mid - low;
        
        root.left = sub(pre, vin, left+1, left+left_num, low, mid-1);
        root.right = sub(pre, vin, left+left_num +1, right, mid+1, high);
        return root;
        
        
    }
}