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

2021年11月25日 阅读数:3
这篇文章主要向大家介绍剑指offer 4. 重建二叉树 & leetcode 剑指 Offer 07. 重建二叉树 & leetcode hot 100 105. 从前序与中序遍历序列构造二叉树,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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

题目描述

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

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

思路:

根据中序遍历和前序遍历能够肯定二叉树,具体过程为:ide

1. 根据前序序列第一个结点肯定根结点函数

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

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

写法一:须要不断赋值拷贝新数组,空间开销较大

 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%spa

复杂度分析:

时间复杂度:对每一个结点都须要进行重建,因此时间复杂度为O(n).net

空间复杂度:创建了一棵树,因此空间复杂度为O(n), 不考虑这个棵树的空间复杂度,那空间复杂度就是递归栈的的大小,也就是树高,最大为O(n), 最小为O(logn)code