leetcode105-从前序与中序遍历序列构造二叉树

原题

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如,给出

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

返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

解法

思想

根据前序遍历第一个元素是根、中序遍历以根为中心划分左子树和右子树的特点,递归构造左子树和右子树。

算法优化过程见:leetcode106-从中序与后序遍历序列构造二叉树

代码

class Solution {
    int[] preorderGlobal;
    Map<Integer,Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        preorderGlobal = preorder;
        map = new HashMap<>();
        for(int i = 0;i < inorder.length; i++) map.put(inorder[i], i);
        if(preorder.length == 0) return null;
        TreeNode root = getUnit(0,preorder.length,0,inorder.length);
        return root;
    }
    public TreeNode getUnit(int preorderStart,int preorderEnd,int inorderStart,int inorderEnd){
        if(preorderStart==preorderEnd) return null;
        TreeNode root = new TreeNode(preorderGlobal[preorderStart]);
        int index = map.get(preorderGlobal[preorderStart]);
        int leftCount = index - inorderStart;
        root.left = getUnit(preorderStart+1,preorderStart+leftCount+1,inorderStart,index);
        root.right = getUnit(preorderStart+leftCount+1,preorderEnd,index+1,inorderEnd);
        return root;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode105-%e4%bb%8e%e5%89%8d%e5%ba%8f%e4%b8%8e%e4%b8%ad%e5%ba%8f%e9%81%8d%e5%8e%86%e5%ba%8f%e5%88%97%e6%9e%84%e9%80%a0%e4%ba%8c%e5%8f%89%e6%a0%91/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月13日
下一篇 2020年1月14日

相关推荐

  • leetcode49-字母异位词分组

    原题 给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。 示例: 输入: ["eat", "tea", "tan", "ate", "nat",…

    算法 2019年12月25日
    0110
  • 剑指offer50-第一个只出现一次的字符

    原题(来源Leetcode) 在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。 示例: s = "abaccdeff" 返回 "b" s…

    算法 2020年6月10日
    0180
  • leetcode101-对称二叉树

    原题 给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树 [1,2,2,3,4,4,3] 是对称的。     1  &nbsp…

    算法 2020年1月11日
    0120
  • leetcode112-路径总和

    原题 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例:  给定如下二叉树,…

    算法 2020年1月12日
    0150
  • leetcode64-最小路径和

    原题 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明: 每次只能向下或者向右移动一步。 示例: 输入: [ [1,3…

    算法 2020年2月24日
    0100
  • 程序员面试金典08.11-硬币

    原题(来源Leetcode) 硬币。给定数量不限的硬币,币值为25分、10分、5分和1分,编写代码计算n分有几种表示法。(结果可能会很大,你需要将结果模上1000000007) 示…

    算法 2020年4月23日
    0170
  • leetcode435-无重叠区间

    原题 给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没…

    算法 2020年2月18日
    02420
  • leetcode100-相同的树

    原题 给定两个二叉树,编写一个函数来检验它们是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: 输入: 1 1 / \ / \ 2 3 2 …

    算法 2020年5月7日
    0210
  • leetcode234-回文链表

    原题 请判断一个链表是否为回文链表。 示例1: 输入: 1->2 输出: false 示例2: 输入: 1->2->2->1 输出: true 进阶: 你能否用 O(n) 时间复杂…

    2019年12月16日
    0120
  • leetcode70-爬楼梯

    原题 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意: 给定 n 是一个正整数。  示例 1: 输入:…

    算法 2020年1月21日
    0850

发表回复

登录后才能评论