剑指Offer07【重建二叉树】递归图解

作者:神秘网友 发布时间:2020-10-30 09:43:59

剑指Offer07【重建二叉树】递归图解

剑指Offer07【重建二叉树】递归图解

目录

    • 题目描述
    • 输入输出
    • 解题思路
    • 图解递归树
    • 代码

??输入某二叉树的前序遍历中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字

输入

前序遍历  preorder = [3,9,20,15,7]
中序遍历  inorder = [9,3,15,20,7]

返回如下的二叉树:
剑指Offer07【重建二叉树】递归图解

限制:0 <= 节点个数 <= 5000

前序遍历特点:节点按照[根节点|左子树|右子树]排序,
??如上例:pre[]=[3|9|20,15,7]
中序遍历特点:节点按照[左子树|根节点|右子树]排序,
??如上例:in[]=[9|3|15,20,7]

递归步骤:

  1. 取前序遍历数组首元素pre[0]=3,该首元素为根节点;
  2. 在中序遍历数组 in[ ] 中找到根节点3的下标 i ,根据中序遍历[左|根|右]的特性,下标[0,i-1]范围对应根节点3的左子树节点;下标[i+1,in.length-1]范围对应根节点3的右子树节点;
  3. 由步骤 2 知左子树节点数目为 i,根据前序遍历[根|左|右]的特性,当pre[0]为根节点时,其左子树节点对应下标为[1,i],其右子树节点对应下标为[i+1,pre.length-1]。
  4. 递归进行上述1,2,3的步骤。每次递归需要截取此时的前序遍历与中序遍历数组。
对于上例输入,递归树如下:

剑指Offer07【重建二叉树】递归图解

根据递归树得到重建的二叉树:

剑指Offer07【重建二叉树】递归图解

Java版本:递归法
import java.util.*;
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));
                root.right=reConstructBinaryTree(
                          Arrays.copyOfRange(pre,i+1,pre.length),
                          Arrays.copyOfRange(in,i+1,in.length));
            }
        }
        return root;
    }
}
注意:
java中java.util.Arrays下的函数:
public static int[] copyOfRange(int[] original,int from, int to)
功能:拷贝原数组original的区间[from,to)内的元素,返回拷贝后的数组。注意拷贝区间左闭右开。

??力扣地址:剑指 Offer 07. 重建二叉树

剑指Offer07【重建二叉树】递归图解相关教程

  1. 剑指offer:旋转数组的最小数字

    剑指offer:旋转数组的最小数字 1.没什么好说的直接排序,输出最小值就完了。暴力直接,有api不用是傻瓜。 public int minNumberInRotateArray(int[] array) { //直接排序 if (array.length == 0) return 0; Arrays.sort(array); return array[0]; } 2.站在学

  2. 【剑指 Offer 】45. 把数组排成最小的数

    【剑指 Offer 】45. 把数组排成最小的数 题目 :45. 把数组排成最小的数 思路 : 根据冒泡法进行组合比较两个字符串拼接在一起两种情况的大小,取结果最小的作为排序结果; 例如,两个字符串s1,s2: 两种拼接方式拼接起来,比较s1s2与s2s1哪个值小? 如果s1s2

  3. 剑指offer第54题 二叉搜索树的第k大节点

    剑指offer第54题 二叉搜索树的第k大节点 文章目录 问题描述: 解题思路: 代码实现: 问题描述: 给定一棵二叉搜索树,请找出其中第k大的节点。 示例 1: 输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2输出: 4 示例 2: 输入: root = [5,3,6,2,4,null,null

  4. 剑指offer第52题 两个链表的第一个公共节点

    剑指offer第52题 两个链表的第一个公共节点 文章目录 问题描述: 解题思路: 代码实现: 问题描述: 输入两个链表,找出它们的第一个公共节点。 如下面的两个链表: 在节点 c1 开始相交。 示例 1: 输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,

  5. python--剑指offer--中等--49. 丑数

    python--剑指offer--中等--49. 丑数 class Solution: def nthUglyNumber(self, n: int) - int: dp = [1] p2 = p3 = p5 = 0 for i in range(1, n): cur2 = dp[p2]*2 cur3 = dp[p3]*3 cur5 = dp[p5]*5 dp.append(min(cur2, cur3, cur5)) if dp[i] == cur2: p2 +

  6. 剑指offer53题 在排序数组中查找数字

    剑指offer53题 在排序数组中查找数字 文章目录 问题一:在排序数组中查找数字 问题描述: 解题思路: 代码实现: 问题二:有序数组中缺失的数字 问题描述: 解题思路: 代码实现: 问题描述: 统计一个数字在排序数组中出现的次数。 示例 1: 输入: nums = [5,7

  7. 【剑指offer】06. 从尾到头打印链表

    【剑指offer】06. 从尾到头打印链表 题目描述 力扣 牛客 // 输入一个链表的头节点,从尾到头反过来返回每个节点// 的值(用数组返回)。 题解 牛客 // 逐元素存储// 时间复杂度:14ms// 空间复杂度:9524KBimport java.util.ArrayList;import java.util.Colle

  8. LeetCode刷题__剑指 Offer 03. 数组中重复的数字

    LeetCode刷题__剑指 Offer 03. 数组中重复的数字 LeetCode 剑指 Offer 03. 数组中重复的数字 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重