剑指OfferJZ4：重建二叉树-java版

ゝ一世哀愁。 2022-10-13 01:55 108阅读 0赞

### 剑指OfferJZ4：重建二叉树-java版 ###

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

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

### 核心思路： ###

**前序遍历：中左右 ——>（特点：靠前的一定是子树的父节点，即“中”）利用前序序列来定位“中”  
中序遍历：左中右 ——>在得到“中”的基础上，利用中序序列来定位“左”“右”**

首先，利用前序序列定位到“中”（根节点）为1，再根据1到中序序列定位节点1的左右子树，如图：左子树包含4 7 2 ；右子树包含5 3 8 6  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70_pic_center]

接着，利用前序序列定位到“中”为2，再根据2到中序序列定位节点2的左右子树，如图：左子树包含：4 7；右子树为空  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70_pic_center 1]

接着，利用前序序列定位到“中”为4，再根据4到中序序列定位节点4的左右子树，如图：左子树为空；右子树为7  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70_pic_center 2]

看，根节点1的左子树全部搞定！所以就不用再操作这步：“利用前序序列定位到“中”为7”了

接着，利用前序序列定位到“中”为3，再根据3到中序序列定位节点3的左右子树，如图：左子树为5；右子树包含：8 6  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70_pic_center 3]  
接着，利用前序序列定位到“中”为5，再根据5到中序序列定位节点5的左右子树，如图：左子树为空；右子树为空，不用画了

接着，利用前序序列定位到“中”为6，再根据6到中序序列定位节点6的左右子树，如图：左子树为8；右子树为空  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70_pic_center 4]

右子树也全部搞定！  
这样我们就根据二叉树的前序遍历和中序遍历重建出了该二叉树！

那么我们根据后序遍历的规则——左右中 便可得出后序序列为 7 4 2 5 8 6 3 1

class TreeNode{ 
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode next;
    
        TreeNode (int x){ 
            val=x;
        }
    }
    
    public class jz4 { 
        private static int index=0;
        private static TreeNode solve(int[] pre,int[] tempIn){ //pre前序序列 tempIn中序序列
            int len1=0;//当前节点的左子树节点个数
            int len2=0;//当前节点的右子树节点个数
            for(int i=0;i<tempIn.length;i++){ 
                if(pre[index]==tempIn[i]){ 
                    break;
                }
                len1++;
            }
            len2=tempIn.length-len1-1;
    
    
            int index1=0;//左子树的下标
            int index2=0;//右子树的下标
            int[] temp1=new int[len1];//当前节点的左子树
            int[] temp2=new int[len2];//当前节点的右子树
            boolean flag=false;//没有找到pre[index]==tempIn[i]的时候
            //往左右子树中添加值
            for(int i=0;i<tempIn.length;i++){ 
                if(pre[index]==tempIn[i]){ 
                    flag=true;
                }else if(!flag){ //没找到，把当前数放到左子树temp1中
                    temp1[index1++]=tempIn[i];
                }else{ //找到了,再往后遍历就都是右子树，把当前数组放到右子树temp2中
                    temp2[index2++]=tempIn[i];
                }
            }
    
            //上面统计了左右子树有哪些后，下面来创建左右子树
            //核心代码
            TreeNode node=new TreeNode(pre[index]);
            node.right=null;
            node.left=null;
            if(index<pre.length && temp1.length>0){ //前序序列没有遍历完，左子树中有值
                index++;//遍历前序序列的下标加一
                node.left=solve(pre,temp1);//创建当前节点的左子树
            }
            if(index<pre.length && temp2.length>0){ //前序序列没有遍历完，右子树中有值
                index++;//遍历前序序列的下标加一
                node.right=solve(pre,temp2);//创建当前节点的右子树
            }
            return node;
        }
    
        public static TreeNode reConstructBinaryTree(int[] pre,int[] in) { 
    
            index=0;//遍历前序序列的下标
            return solve(pre, in);
        }
    
        public static void main(String[] args) { 
            int[] pre={ 1,2,4,7,3,5,6,8};//前序遍历
            int[] in={ 4,7,2,1,5,3,8,6};//中序遍历
            TreeNode root=reConstructBinaryTree(pre,in);
    
            //测试---------------测试
            //前序遍历
            dfs1(root);
            System.out.println();
            //中序遍历
            dfs2(root);
            System.out.println();
            //后序遍历
            dfs3(root);
            System.out.println();
    
        }
    
        private static void dfs1(TreeNode node){ 
            //前序遍历——中左右
            System.out.printf("%d",node.val);
            if(node.left!=null){ 
                dfs1(node.left);
            }
            if(node.right!=null){ 
                dfs1(node.right);
            }
    
        }
        private static void dfs2(TreeNode node){ 
            //中序遍历——左中右
            if(node.left!=null){ 
                dfs2(node.left);
            }
            System.out.printf("%d",node.val);
            if(node.right!=null){ 
                dfs2(node.right);
            }
    
        }
        private static void dfs3(TreeNode node){ 
            //后序遍历——左右中
            if(node.left!=null){ 
                dfs3(node.left);
            }
            if(node.right!=null){ 
                dfs3(node.right);
            }
            System.out.printf("%d",node.val);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][20210705212033702.gif_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221005/d863f5d1b0de4a8491a71b5f2901056b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221005/ae13918ced574569ae8e043b8ec7f7b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221005/bfae106995654e93846002500fd5f1e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221005/14552bf89b8e4063b06e4b6abca5c8b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221005/339004d6b105430dbf31290ca7d344b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221005/ac595fd855104e82a850bc5c4812c3c9.png
[20210705212033702.gif_pic_center]: /images/20221005/f91e90164b104850ad8781fd16a6f811.png