剑指offer 4. 重建二叉树 & leetcode 剑指 Offer 07. 重建二叉树 & leetcode hot 100 105. 从前序与中序遍历序列构造二叉树

4. 重建二叉树 & 剑指 Offer 07. 重建二叉树 & 105. 从前序与中序遍历序列构造二叉树

题目描述

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

解法来源：https://blog.nowcoder.net/n/2cbe9f458bd74be1a910aa6d071aa411?f=comment

思路：

根据中序遍历和前序遍历可以确定二叉树，具体过程为：

1. 根据前序序列第一个结点确定根结点

2. 根据根结点在中序序列中的位置分割出左右两个子序列

3. 对左子树和右子树分别递归使用同样的方法继续分解

写法一：需要不断赋值拷贝新数组，空间开销较大

 1 import java.util.Arrays;
 2 public class Solution {
 3     // 递归将中序遍历和前序遍历数组变成分成子树的 前序 遍历和 中序遍历的数组
 4     public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
 5         if(pre.length == 0 || in.length == 0){
 6             return null;
 7         }
 8         // 创建根节点
 9         TreeNode root = new TreeNode(pre[0]);
10         
11         // 从中序遍历中找到根节点，
12         for(int i = 0; i < in.length; i++){
13             if(in[i] == pre[0]){
14                 // 左子树，注意copyOfRange的区间范围，左闭右开
15                 root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
16                 // 右子树
17                 root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
18             }
19         }
20         return root;
21     }
22 }

写法二：借助一个辅助函数，不需创建临时数组，空间开销较小

 1 class Solution {
 2     public TreeNode buildTree(int[] preorder, int[] inorder) {
 3         if(preorder == null || inorder == null){
 4             return null;
 5         }
 6         return helpBuildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
 7     }
 8 
 9 
10     public TreeNode helpBuildTree(int[] preorder, int preLeft, int preRight, int[] inorder, int midLeft, int midRight){
11         // 从preorder中取出头结点，在inorder中找到这个根节点，inorder中根节点左边的是左子树，右边的是右子树
12         // 根据inorder左子树的结点个数去preorder中找到这么多个数作为左子树，剩下的作为右子树
13         if(preLeft > preRight || midLeft > midRight){   // 如果没有元素，直接返回空节点
14             return null;
15         }
16         // 用preorder的第一个结点作为根节点，创建一个结点
17         TreeNode root = new TreeNode(preorder[preLeft]);
18         // 在inorder中找到这个根节点，inorder中根节点左边的是左子树，右边的是右子树
19         int index = midLeft;
20         for(; index <= midRight && inorder[index] != preorder[preLeft]; index++);
21 
22         // 根据inorder左子树的结点个数去preorder中找到这么多个数作为左子树，剩下的作为右子树
23         root.left = helpBuildTree(preorder, preLeft + 1, preLeft + index - midLeft, inorder, midLeft, index - 1);
24         root.right = helpBuildTree(preorder, preLeft + index - midLeft + 1, preRight, inorder, index + 1, midRight);
25         return root;
26     }
27 }

leetcode 运行时间为4 ms > 48.09%, 内存消耗：39.1 MB > 61.15%

复杂度分析：

时间复杂度：对每个结点都需要进行重建，所以时间复杂度为O(n)

空间复杂度：建立了一棵树，所以空间复杂度为O(n), 不考虑这个棵树的空间复杂度，那空间复杂度就是递归栈的的大小，也就是树高，最大为O(n), 最小为O(logn)