105.从中序与前序遍历序列构造二叉树

题目描述

题解

递归

这道题方法与106题一模一样, 只是遍历的顺序有所变化而已, 具体查看106题解

public class lc105 {
    int[] preorder;
    HashMap<Integer, Integer> map;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.map = new HashMap<>();

        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }

        return helper(0, preorder.length - 1, 0, inorder.length - 1);

    }

    private TreeNode helper(int ps, int pe, int ls, int le) {
        if (ps > pe || ls > le) {
            return null;
        }

        int val = preorder[ps];
        TreeNode root = new TreeNode(val);
        int li = map.get(val);

        root.left = helper(ps + 1, ps + li - ls, ls, li - 1);
        root.right = helper(ps + li - ls + 1, pe, li + 1, le);
        return root;
    }

}