本周已经进入倦怠期，题目完成总量120，需要温故知新了。

通过先序遍历和后序遍历构造二叉树

889. Construct Binary Tree from Preorder and Postorder Traversal
这道题的核心思路，是找到根节点，然后根据根节点将数组分成左子树与右子树。
拿官方的例子来解释，pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
先序遍历的顺序：根节点-左子节点-右子节点
后续遍历的顺序：左子节点-右子节点-根节点
第一步，拿到先序遍历的第一个元素1，为根节点，随后它的左子节点应为是第二个元素2；通过左子节点将后续遍历的数组分割为[4,5,2],[6,7,3]；因为1已经被使用了，所以应该剔除。
第二步，pre=[2,4,5],post=[4,5,2]，进一步拿出根节点2，然后分为[4,5],[4,5]；
第三步，分割为单个元素，创建节点并返回；这样就构造了一颗子树了。

t1.png

/**
 * 889. Construct Binary Tree from Preorder and Postorder Traversal
 *
 * Return any binary tree that matches the given preorder and postorder traversals.
 *
 * Values in the traversals pre and post are distinct positive integers.
 *
 * Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
 * Output: [1,2,3,4,5,6,7]
 *
 * pre:root-left-right
 * post:left-right-root
 */
public class ConstructBinaryTreefromPreorderandPostorderTraversal {
    public void test(){
        int[] pre1 = {1,2,4,5,3,6,7};
        int[] post1 = {4,5,2,6,7,3,1};
        TreeNode.preorderTraversal(constructFromPrePost(pre1,post1));
    }
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        return buildTree(pre,0,pre.length-1,post,0,post.length-1);
    }
    TreeNode buildTree(int[] pre,int pStart,int pEnd,int[] post,int poStart,int poEnd){
        if(pStart > pEnd || poStart > poEnd){
            return null;
        }
        TreeNode node = new TreeNode(pre[pStart]);
        if(pStart == pEnd){
            return node;
        }
        int nextIndex = poStart;
        for(;nextIndex<=poEnd;nextIndex++){
            if(pre[pStart+1] == post[nextIndex]){
                break;
            }
        }

        node.left = buildTree(pre,pStart+1,pStart+1+nextIndex-poStart,post,poStart,nextIndex);
        node.right = buildTree(pre,pStart+1+nextIndex-poStart +1,pEnd,post,nextIndex+1,poEnd-1);
        return node;
    }
}

通过中序遍历以及后序遍历生成树

106. Construct Binary Tree from Inorder and Postorder Traversal
这个题的思路也是如上题，计算左子树与右子树的区间
中序：左-根-右
后序：左-右-根
in = {9,3,15,20,7};post = {9,15,7,20,3};
后序遍历最后一个元素必然是树的根节点，找到3，并在中序遍历中将数组分为[9],[15,20,7]两部分，进而再对两部分进行递归。

/**
 * 106. Construct Binary Tree from Inorder and Postorder Traversal
 *
 * Given inorder and postorder traversal of a tree, construct the binary tree.
 *
 * Note:
 * You may assume that duplicates do not exist in the tree.
 * @author ctk
 */
public class ConstructBinaryTreefromInorderandPostorderTraversal {
    public void test(){
        //   3
        //   / \
        //  9  20
        //    /  \
        //   15   7
        int[] inorder1 = {9,3,15,20,7};
        int[] postorder1 = {9,15,7,20,3};
        traversal(buildTree(inorder1,postorder1));
    }
    private void traversal(TreeNode tree){
        if(tree == null){
            return;
        }
        System.out.println(tree.val);
        traversal(tree.left);
        traversal(tree.right);
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        Map<Integer,Integer> valueIndex = new HashMap<>();
        for(int i=0;i<inorder.length;i++){
            valueIndex.put(inorder[i],i);
        }
        return buildTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1,valueIndex);
    }
    private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd,Map<Integer,Integer> valueIndex){
        if(inStart > inEnd || postStart > postEnd){
            return null;
        }
        TreeNode root = new TreeNode(postorder[postEnd]);
        int rootIndex = valueIndex.get(postorder[postEnd]);
        root.left = buildTree(inorder,inStart,rootIndex-1,postorder,postStart,postStart+(rootIndex-inStart-1),valueIndex);
        root.right = buildTree(inorder,rootIndex+1,inEnd,postorder,postStart+rootIndex-inStart,postEnd-1,valueIndex);
        return root;
    }
}

通过中序遍历以及前序遍历生成树

105. Construct Binary Tree from Preorder and Inorder Traversal

中序：左-根-右
前序：根-左-右
通过根节点，将数组分割进而递归

/**
 * 105. Construct Binary Tree from Preorder and Inorder Traversal
 * Given preorder and inorder traversal of a tree, construct the binary tree.

 * Note:
 * You may assume that duplicates do not exist in the tree.
 * Created by MacBook on 2019/12/1.
 */
public class ConstructBinaryTreefromPreorderandInorder {
    public void test(){
        /*
                3
               / \
              9  20
                /  \
               15   7
        */
        int[] pre1 = {3,9,20,15,7};
        int[] in1 = {9,3,15,20,7};
        TreeNode.preorderTraversal(buildTree(pre1,in1));
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    public TreeNode buildTree(int[] preorder,int preStart,int preEnd,int[] inorder,int inStart,int inEnd){

        if(inStart > inEnd || preStart > preEnd){
            return null;
        }
        int rootVal = preorder[preStart];
        int rootIndex = inStart;
        while (rootIndex < inEnd){
            if(inorder[rootIndex] == rootVal) {
                break;
            }
            rootIndex ++;
        }
        TreeNode root = new TreeNode(rootVal);
        root.left = buildTree(preorder,preStart+1,preStart+rootIndex-inStart,inorder,inStart,rootIndex-1);
        root.right = buildTree(preorder,preStart+rootIndex-inStart+1,preEnd,inorder,rootIndex+1,inEnd);
        return root;
    }
}

计算元素之后小于它的总数

315. Count of Smaller Numbers After Self
题目主旨是给定一个数组a[],计算出每一个元素之后出现的小于它的元素的个数。
使用树状数组统计，首先对原数组拷贝一份并排序，然后用BIT记录它对应位置的个数，每次遍历到的元素就能统计到小于它的元素的个数。

image.png image.png

因此，我们使用从后往前遍历的方式，每次访问元素先获取BIT中比它还小的个数统计，然后再讲其更新到BIT中。

/**
 * 315. Count of Smaller Numbers After Self
 *
 * You are given an integer array nums and you have to return a new counts array.
 * The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
 */
public class CountofSmallerNumbersAfterSelf {
    public void test(){
        int[] nums1 = {5,2,6,1};
        System.out.println(countSmaller(nums1));
        int[] nums2 = {-1,-1};
        System.out.println(countSmaller(nums2));
    }

    /**
     * Binary Indeed Tree
     */
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> result = new ArrayList<>(nums.length);
        int[] copy = new int[nums.length];
        for(int i=0;i<nums.length;i++){
            copy[i] = nums[i];
        }

        int[] bit = new int[nums.length + 1];

        Arrays.sort(copy);

        for(int i=nums.length-1;i>=0;i--){
            result.add(query(bit,binarySearch(copy,nums[i])-1));
            update(bit,binarySearch(copy,nums[i]),1);
        }
        Collections.reverse(result);
        return result;
    }
    int lowBit(int i){
        return i & (-i);
    }
    int query(int[] bit,int x){
        int res = 0;
        int i = x + 1;
        while (i>0){
            res += bit[i];
            i -= lowBit(i);
        }
        return res;
    }
    void update(int[] bit,int x,int value){
        int i = x + 1;
        while (i<bit.length){
            bit[i] += value;
            i += lowBit(i);
        }
    }
    int binarySearch(int[] sortArray,int value){
        int n = sortArray.length;
        int l = 0;
        int r = n - 1;
        while (l < r){
            int mid = l + (r - l) / 2;
            if(sortArray[mid] > value){
                r = mid - 1;
            }else if(sortArray[mid] < value){
                l = mid + 1;
            }else {
                return mid;
            }
        }
        return sortArray[l] == value ? l : -1;
    }
}