106.从中序与后序遍历序列构造二叉树

题目描述

题解

递归

这道题要明白中序和后序遍历的顺序和相关特点.

对于后续遍历来说, 最后一个元素一定是根节点的数值, 在中序遍历的结果中找出该值, 那么这个位置之前的数组就是左子树的遍历结果, 这个位置之后的数组就是右子树的遍历结果.

那么根据这个数量关系就可以进行递归操作:

拿到一个后序遍历的数组后, 先找出根节点的数值, 也就是最后一个元素

然后在中序遍历的数组中找到该元素的位置, 确定下来左右子树的遍历结果

分别将左右子树的遍历结果传递下去

public class lc106 {
    private int[] postorder;
    private HashMap<Integer, Integer> map;

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

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

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

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

        int val = postorder[pe];
        TreeNode root = new TreeNode(val);
        int li = map.get(val);

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