[16-20][剑指offer]二叉树的镜像， 构建乘积数组，调

二叉树的镜像

时间：2019年6月21日09:24:27
难度：简单
编号：16
进度：1/5 25/52
语言：java
类型：递归，二叉树
题目来源：牛客网

思路：最简单的题了，就不多说了。有个小坑，当节点为null的时候，返回值应该是return ; 不要写成 return null;

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public void Mirror(TreeNode root) {
        TreeNode temp = null;
        if(root == null){
            return ;
        }
        temp = root.left;
        root.left = root.right;
        root.right = temp;
        if(root.left!=null){
            Mirror(root.left);
        }
        if(root.right!=null){
            Mirror(root.right);
        }
            
        
    }
}

运行时间：28ms
占用内存：9552k

---

构建乘积数组

时间：2019年6月21日09:56:09
难度：简单
编号：17
进度：2/5 25/52
语言：c++
类型：数组
题目来源：牛客网

思路：这题可以用动态规划的思路去做；
这里把B数组看成两个部分，
B[i] = B[0]+B[1]+...+B[i-1] + B[i+1]+....+B[n-1]
画出矩阵图可知，B数组组成了两个三角形 ，前半部分是一个上三角，后半部分是一个下三角
前半部分从前往后相乘
后半部分从后往前相乘

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int n = A.size();
        vector<int> b(n);
        b[0] = 1;
        for(int i =1; i<n;i++){
            b[i] = b[i-1]*A[i-1];
        }
        int temp = 1;
        for(int i = n-2;i>=0;i--){
            temp *=A[i+1];
            b[i] *=temp;
        }
        return b;
    }
};

调整数组顺序使奇数位于偶数前面

时间：2019年6月21日10:51:25
难度：简单
编号：18
进度：3/5 25/52
语言：c++
类型：数组
题目来源：牛客网

---

思路：用空间换时间，很简单

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        # 空间换时间
        # 时间O（n）
        # 空间O（n）
        odd,even =[],[]
        for each in array:
            if each%2 ==0:
                even.append(each)
            else:
                odd.append(each)
        return odd+even

---

矩形覆盖

时间：2019年06月22日11:30:37
难度：简单
编号：19
进度：4/5 25/52
语言：python
类型：斐波那契数列，脑筋急转弯
题目来源：牛客网

思路：斐波那契数列
时间复杂度：
空间复杂度：

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        if number<=1:
            return number
        a,b = 1,1
        for each in range(1,number):
            a,b = b,a+b
        return b

---

119. 杨辉三角 II

时间：2019年6月22日14:56:39
难度：简单
编号：20
进度：5/5 25/52
语言：python
类型：杨辉三角，迭代
题目来源：leetcode

思路：迭代即可
时间复杂度：
空间复杂度：

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        if rowIndex == 0:
            return [1]
        if rowIndex ==1:
            return [1,1]
        ans = [1,1]
        data = [1]
        for index in range(2,rowIndex+1):
            data = [1]
            for i in range(0,index-1):
                data.append(ans[i]+ans[i+1])
            data.append(1)
            ans = data
            
        return data

118. 杨辉三角

class Solution:
    def generate(self, rowIndex: int) -> List[List[int]]:
        if rowIndex == 0:
            return [[1]]
        ans = [1,1]
        data = [1]
        res = [[1],[1,1]]
        if rowIndex ==1:
            return res

        for index in range(2,rowIndex):
            data = [1]
            for i in range(0,index-1):
                data.append(ans[i]+ans[i+1])
            data.append(1)
            ans = data
            res.append(data)
            
        return res