根据前序遍历和中序遍历重建二叉树

落日映苍穹つ 2022-06-17 08:38 178阅读 0赞

/**
         * Definition for binary tree
         */
        public class TreeNode {
              int val;
              TreeNode left;
              TreeNode right;
              TreeNode(int x) { val = x; }
         }
    
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
            //创建新节点
            TreeNode node = new TreeNode(0);
            //判断是否为空
            if (pre.length == 0  || in.length == 0){
                return null;
            }else {
                node.val = pre[0];
            }
            int[] p_left,p_right,left_num,right_num;
    
                for (int j = 0; j < in.length; j++) {
                         if (pre[0] == in[j]){
                             //获取前序遍历左子树 p_left = Arrays.copyOfRange(pre,0,j); 数组复制范围
                             p_left = new int[j];
                             for (int k = 0; k < j; k++) {
                                 p_left[k] = pre[k+1];
                             }
                             //获取前序遍历右子树
                             p_right = new int[pre.length -j-1];
                             for (int k = 0; k < pre.length -j-1; k++) {
                                 p_right[k] = pre[k+j+1];
                             }
                             //获取中序遍历左子树
                             left_num = new int[j];
                             for (int k = 0; k < j; k++) {
                                 left_num[k] = in[k];
                             }
                             //获取中序遍历右子树
                             right_num = new int[in.length-j-1];
                             for (int k = 0; k < in.length-j-1; k++) {
                                 right_num[k] = in[k+j+1];
                             }
    
                             node.left = reConstructBinaryTree(p_left,left_num);
                             node.right = reConstructBinaryTree(p_right,right_num);
                         }
                }
    
                return node;
            }