[数据结构与算法]根据二叉树的先序、中序、后序遍历确定二叉树

根据二叉树的先序，中序，后序遍历确定二叉树

我们知道根据二叉树的先序和中序或者是二叉树的中序和后序能够确定唯一的一棵二叉树，先记录一下java实现代码

二叉树的先序和中序遍历确定二叉树
我们能够知道先序的第一个节点是根节点，此时根据根节点去找在中序遍历中的位置，左边就是左子树的节点，右边就是右子树的节点，那么我们可以把先序和中序序列中的左右子树节点的序列范围找到，然后递归继求解遍历，最后完成二叉树的构建，例如：
先序：{1，5，3，2，7}
中序：{3，5，2，1，7}
此时能进行划分有：
根节点{1}
左子树：先序：{5，3，2} ?中序：{3，5，2}
右子树：先序：{7} ????????????中序：{7}
然后对左子树进行递归，此时有：
根节点：{5}
左子树：先序：{3} ?中序 {3}
右子树：先序：{2} ?中序 {2}
当递归到空的时候，返回null值，否则就按照类似上述逻辑递归左右子树建树就能完成二叉树的构建

java实现

 public static int find(int[] arr,int num){ //查找根节点在中序遍历数组中的位置
        for(int i=0;i<arr.length;i++){
            if(arr[i]==num) return i;
        }
        return -1;
}
 public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0||inorder.length==0) return null;//空节点
        TreeNode node = new TreeNode(preorder[0]);
        int left = find(inorder,preorder[0]);  
        node.left = buildTree(Arrays.copyOfRange(preorder,1,left+1),Arrays.copyOfRange(inorder,0,left));
        node.right = buildTree(Arrays.copyOfRange(preorder,left+1,preorder.length),Arrays.copyOfRange(inorder,left+1,inorder.length));
        return node;
 }

使用HashMap和下标控制，速度更快

 public HashMap<Integer,Integer> map;
 public int[] preorder_;
    public TreeNode dfs_new(int root,int left,int right){
        if(left>right||root>=preorder_.length) return null;
        TreeNode p = new TreeNode(preorder_[root]);
        int site = map.get(preorder_[root]);
        p.left = dfs_new(root+1,left,site-1);
        p.right = dfs_new(root+site-left+1,site+1,right);
        return p;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0) return null;
        map = new HashMap<>();
        preorder_ = new int[preorder.length];
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
            this.preorder_[i] = preorder[i];
        }
        return dfs_new(0,0,inorder.length-1);
    }

二叉树的中序和后序遍历确定二叉树
利用中序和后序遍历确定二叉树的过程和利用先序和中序的过程类似，只是此时每次判断的根节点是后序数组的最后一个，例如：
中序：{3，5，2，1，7}
后序：{3，2，5，7，1}
此时进行划分有，
根节点：{1}
左子树：中序：{3，5，2} ?后序：{3，2，5}
右子树：中序：{7}?????????????后序：{7}
然后对左子树进行递归处理，此时有：
根节点：{5}
左子树：中序：{3}?后序：{3}
右子树：中序：{2}?后序：{2}
当递归到数组顺序为空时返回null，否则按照上述流程对左右子树递归处理进行构建二叉树

java实现

 public static int find(int[] arr,int target){//查找根节点在后序遍历数组中的位置
        for(int i=0;i<arr.length;i++){
            if(arr[i]==target) return i;
        }
        return -1;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder.length==0||inorder.length==0) return null;//空节点
        TreeNode node = new TreeNode(postorder[postorder.length-1]);
        int left = find(inorder,postorder[postorder.length-1]);  
        node.left = buildTree(Arrays.copyOfRange(inorder,0,left),Arrays.copyOfRange(postorder,0,left));
        node.right = buildTree(Arrays.copyOfRange(inorder,left+1,inorder.length),Arrays.copyOfRange(postorder,left,postorder.length-1));
        return node;
    }