8月算法训练------第十天（分治算法）解题报告

题目类型：分治算法
题目难度：中等

第一题、剑指 Offer 07. 重建二叉树

1. 题目链接：剑指 Offer 07. 重建二叉树
2. 思路分析：
   我们知道，二叉树的前序遍历和中序遍历能确定唯一一个二叉树，找到前序遍历的第一个节点，这个节点就是根节点，然后在中序遍历中找到这个节点，这个节点左边的就是根节点的左子树，右边的就是根节点的右子树。
   具体方法就是将中序遍历的序列存到一个HashMap中，将中序遍历的索引号记住，用这个索引号来确定根节点的左右子树，左子树就是从开始位到根节点的前一位，右子树就是中序遍历的右边一位到当前子树的最后一位。
3. 代码：

class Solution {
    int[] preorder;
    HashMap<Integer, Integer> dic = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0; i < inorder.length; i++)
            dic.put(inorder[i], i);
        return recur(0, 0, inorder.length - 1);
    }
    TreeNode recur(int root, int left, int right) {
        if(left > right) return null;                          // 递归终止
        TreeNode node = new TreeNode(preorder[root]);          // 建立根节点
        int i = dic.get(preorder[root]);                       // 划分根节点、左子树、右子树
        node.left = recur(root + 1, left, i - 1);              // 开启左子树递归
        node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
        return node;                                           // 回溯返回根节点
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

第二题、剑指 Offer 16. 数值的整数次方

1. 题目链接：剑指 Offer 16. 数值的整数次方
2. 思路分析：
   原先用的就是最笨的方法，就是运用循环，将数x连续乘n次。但最后发现，一旦n的值变大，就会超出时间限制，这说明这种方法就不是这题所想要的解法。
   看了眼答案，自己也想了想，确实答案上的方法是很好的，就是用快速幂算法，这种方法将时间复杂度降为O(log n)，这种方法确实很巧妙，自己确实学到了。
   当n为偶数时，说明只需要将算出的幂值相乘；当n的值为奇数时，说明不仅需要将幂值相乘还需要再乘一个x，以达到要求。
   统一成一个方法p，当幂数为负数时，只需将1 / p(x, -n)，这样就可以将n统一成一个正数处理了。
3. 代码：

class Solution {
    public double myPow(double x, int n) {
        return n > 0 ? p(x, n) : 1 / p(x, -n);
    }
    public double p(double x, int N){
        if(N == 0){
            return 1;
        }
        double y = p(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

第三题、剑指 Offer 33. 二叉搜索树的后序遍历序列

1. 题目链接：剑指 Offer 33. 二叉搜索树的后序遍历序列
2. 思路分析：
   对于这个二叉搜索树，当其进行后续遍历时，最后一个值j一定是二叉树的根节点，这时只需要遍历数组，找出比最后一个值大的值的下标m，m之前的值就是根节点的左子树，m之后的值肯定就是根节点的右子树，这时只需要将判断二叉树的左子树是否都小于根节点j，并且右子树是否都大于其根节点。
   因为我们已经判断过其左子树必定都小于其根节点，所以现在只需确定是否右节点的值都是否大于其根节点，具体方法是：遍历二叉树的右节点序列，当序列值大于根节点时，就让标记值p++，当右节点小于某一值不大于根节点时，就停止循环，这时就判断标记值p与根节点下标的值j是否相等，就能判断其右节点是否符合条件，如此进行递归。
   递归的终止条件是：当i>j时，这时就直接返回true。
3. 代码：

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return cur(postorder, 0, postorder.length-1);
    }
    public boolean cur(int[] postorder, int i, int j){
        if(i > j) return true;
        int p = i;
        while(postorder[p] < postorder[j]){
            p++;
        }
        int m = p;
        while(postorder[p] > postorder[j]){
            p++;
        }
        return p==j && cur(postorder, i, m-1) && cur(postorder, m, j-1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17