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/

发表回复

登录后才能评论