力扣：从中序与后序遍历序列构造二叉树java_java根据中序遍历和后序遍历生成二叉树

力扣：从中序与后序遍历序列构造二叉树java

流程：

中序与后序构造二叉树java

使用递归

递归三部曲：

设置参数和返回值：参数为中序数组和后序数组，返回值为二叉树节点
结束条件：后序数组长度为0则返回null，后序长度为0则说明没有节点，则返回null
单层递归逻辑：
1.创建一个二叉树节点root，对其赋值为后序节点的最后一位节点
再次判断后序数组是否为1，为1说明只有一个节点，则直接返回新创建的root
2.循环查找到root在中序中的位置i
3.分割：对中序数组进行分割，i之前为左子树的中序数组，i之后为右子树的中序数组。
对后序数组分割，0到左子树的中序数组的长度-1为左子树的后序数组，左子树的中序数组的长度到最后第二位为右子树的后序数组
4.递归，对root节点的左子树赋值为递归函数（左子数中序和后序）
对root节点的右子树赋值为递归函数（左子数中序和后序）
5.最后返回root节点

代码

class Solution {
    public int[] copyRange(int[] shuzu,int start,int end){//拷贝范围数组到新数组
        
        int len = end - start + 1;
        int[] newshuzu  = new int[len];
        for(int i=start;i<=end;i++){
            newshuzu[i-start] = shuzu[i];
        }
        return newshuzu;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //主递归函数，参数为中序数组和后序数组，返回值为root根节点
        if(postorder.length==0) return null;//结束条件，后序数组长度为0则返回null节点
        TreeNode root = new TreeNode();//创建一个root节点
        root.val = postorder[postorder.length-1];//节点赋值为后序数组的最后一位
        if(postorder.length==1) return root;//后序数组长度为1，则说明只有一个节点了，直接返回root
        int i;//找到中序数组的该root节点的位置
        for(i=0;i<inorder.length;i++){
            if(inorder[i]==root.val){
                break;
            }
        }
        //分割，使用左闭右闭
        int[] lZ = copyRange(inorder,0,i-1);//左节点中序
        int[] lH = copyRange(postorder,0,lZ.length-1);//左节点后序
        int[] rZ = copyRange(inorder,i+1,inorder.length-1);//右节点中序
        int[] rH = copyRange(postorder,lZ.length,postorder.length-2);//左节点后序
        root.left = buildTree(lZ,lH);//递归获取左子树
        root.right = buildTree(rZ,rH);//递归获取右子树
        return root;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

中序与前序构造二叉树java
不同点：
1.每次获取节点变为前序的0下标节点
2.对分割先序的方式改变

class Solution {
    public int[] copyRange(int[] shuzu,int start,int end){
        //新数组赋值传入范围的数组
        int len = end - start + 1;
        int[] newshuzu  = new int[len];
        for(int i=start;i<=end;i++){
            newshuzu[i-start] = shuzu[i];
        }
        return newshuzu;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0) return null;
        TreeNode root = new TreeNode();
        root.val = preorder[0];//根节点不同
        if(preorder.length==1) return root;
        int i;
        for(i=0;i<inorder.length;i++){
            if(inorder[i]==root.val){
                break;
            }
        }
        //分割，先序分割参数不同
        int[] lZ = copyRange(inorder,0,i-1);//左节点中序
        int[] lQ = copyRange(preorder,1,lZ.length);//左节点前序
        int[] rZ = copyRange(inorder,i+1,inorder.length-1);//右节点中序
        int[] rQ = copyRange(preorder,lZ.length+1,preorder.length-1);//左节点前序
        root.left = buildTree(lQ,lZ);
        root.right = buildTree(rQ,rZ);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31