leetcode106-从中序与后序遍历序列构造二叉树

原题

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

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

例如,给出

中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

解法

思想

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

代码

我们逐渐来优化时间复杂度:

第一版,较好懂:

class Solution {
    public int indexOf(int target,int[] order){
        for(int i = 0;i<order.length;i++){
            if(order[i] == target) return i;
        }
        return -1;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder.length == 0) return null;
        TreeNode root = getUnit(inorder,postorder);
        return root;
    }
    public TreeNode getUnit(int[] inorder,int[] postorder){
        if(postorder.length == 0) return null;
        TreeNode root = new TreeNode(postorder[postorder.length-1]);
        int index = indexOf(postorder[postorder.length-1],inorder);
        int[] leftpartInorder = Arrays.copyOfRange(inorder,0,index);
        int[] rightpartInorder = Arrays.copyOfRange(inorder,index+1,inorder.length);
        int leftCount = leftpartInorder.length;
        int[] leftpartPostorder = Arrays.copyOfRange(postorder,0,leftCount);
        int[] rightpartPostorder = Arrays.copyOfRange(postorder,leftCount,postorder.length-1);
        root.left = getUnit(leftpartInorder,leftpartPostorder);
        root.right = getUnit(rightpartInorder,rightpartPostorder);
        return root;
    }
}

第二版,不用再复制数组,直接在原数组上操作:

class Solution {
    int[] inorderGlobal;
    int[] postorderGlobal;
    public int indexOf(int target,int start,int end){
        for(int i = 0;i<end-start;i++){
            if(inorderGlobal[i+start] == target) return i+start;
        }
        return -1;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        inorderGlobal = inorder;
        postorderGlobal = postorder;
        if(postorder.length == 0) return null;
        TreeNode root = getUnit(0,inorder.length,0,postorder.length);
        return root;
    }
    public TreeNode getUnit(int inorderStart,int inorderEnd,int postorderStart,int postorderEnd){
        if(postorderEnd==postorderStart) return null;
        TreeNode root = new TreeNode(postorderGlobal[postorderEnd-1]);
        int index = indexOf(postorderGlobal[postorderEnd-1],inorderStart,inorderEnd);
        int leftCount = index-inorderStart;
        root.left = getUnit(inorderStart,index,postorderStart,leftCount+postorderStart);
        root.right = getUnit(index+1,inorderEnd,postorderStart+leftCount,postorderEnd-1);
        return root;
    }
}

第三版,既然经常要用查找元素在中序遍历中的位置,可以不需要使用indexOf函数,而是一开始则将对应关系保存在哈希表中:

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

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode106-%e4%bb%8e%e4%b8%ad%e5%ba%8f%e4%b8%8e%e5%90%8e%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月12日
下一篇 2020年1月13日

相关推荐

  • leetcode198-打家劫舍

    原题 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会…

    算法 2020年5月29日
    060
  • 蓝桥杯试题-哈夫曼树

    原题 Description Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。 给出一列数{pi}={p0, p1, …, pn-1},用这列…

    算法 2020年3月1日
    0250
  • leetcode77-组合

    原题 给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], […

    算法 2020年5月12日
    0650
  • leetcode540-有序数组中的单一元素

    原题 给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。 示例1: 输入: [1,1,2,3,3,4,4,8,8] 输出: 2 示例2: 输入…

    2020年2月25日
    0700
  • leetcode116-填充每个节点的下一个右侧节点指针

    原题 给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下: struct Node {   int val;  &…

    2020年1月14日
    0530
  • leetcode111-二叉树的最小深度

    原题 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,nul…

    算法 2020年3月25日
    0220
  • leetcode85-最大矩形

    原题 给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 示例: 输入: [   ["1","0","1","0","0"…

    2020年1月24日
    0200
  • leetcode263-丑数

    原题 编写一个程序判断给定的数是否为丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例1: 输入: 6 输出: true 解释: 6 = 2 × 3 示例2: 输入: …

    算法 2020年2月6日
    0120
  • leetcode239-滑动窗口最大值

    原题 给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最…

    算法 2020年4月21日
    0180
  • leetcode136-只出现一次的数字

    原题 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明: 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗…

    算法 2019年12月18日
    0150

发表回复

登录后才能评论