04 图解剑指Offer 重建二叉树 Java题解

向右看齐 2023-02-20 07:35 1阅读 0赞

### 04 图解剑指Offer 重建二叉树 Java题解 ###

*  04 图解剑指Offer 重建二叉树 Java题解
 *   *   *  题目链接
         *  题目描述
         *  题解:
         *  图解:
         *  代码:
         *  复杂度

# 04 图解剑指Offer 重建二叉树 Java题解 #

### [题目链接][Link 1] ###

### 题目描述 ###

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

### 题解: ###

思路:二叉树问题 要用分治法。将重建二叉树分成重建左子树，右子树。  
递归函数的参数有两个一个是前序遍历数组，一个是中序遍历数组。每次递归参数都是左右子树的前序遍历和中序遍历数组。利用Arrays.copyOfRange(pre,start,end);得到子树的数组。每次迭代其实就是找到一次根节点。

1.  如果 前序或中序遍历数组长度等于0 直接返回 null
2.  新建一个节点对象，二叉树根节点为前序遍历数组的第一个元素。
3.  for循环在中序遍历中找到根节点的值，i为索引。
4.  左子树的根节点 = 递归 ，参数左子树数组
5.  右子树的根节点 = 递归， 参数为右子树数组
6.  左右子树数组用Arrays.copyOfRange(pre,start,end)方法， 左闭右开。左边为数组第一个元素索引，右边为数组最后一个元素的索引的下一个索引。

### 图解: ###

![https://img-blog.csdnimg.cn/20200623235120162.png?x-oss-process=image/watermark,type\_ZmFuZ3poZW5naGVpdGk,shadow\_10,text\_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3,size\_16,color\_FFFFFF,t\_70][https_img-blog.csdnimg.cn_20200623235120162.png_x-oss-process_image_watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]

### 代码: ###

/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    import java.util.Arrays;
    public class Solution { 
    public TreeNode reConstructBinaryTree(int [] pre, int [] in) { 
        if(pre.length == 0 || in.length == 0) return null;
            
        TreeNode root = new TreeNode(pre[0]);
        
        for(int i = 0; i < in.length; i++){ 
                if(in[i] == pre[0]) { 
                    root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                    // 右子树，注意 copyOfRange 函数，左闭右开
                    root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
                    break;
                }
            }
        return root;
        }
    }

### 复杂度 ###

空间复杂度O(n) 两个数组  
最坏时间复杂度:O(n)

[Link 1]: https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[https_img-blog.csdnimg.cn_20200623235120162.png_x-oss-process_image_watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200624201810677.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3,size_16,color_FFFFFF,t_70