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/