/** 
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return              -1 if num is lower than the guess number
 *                   1 if num is higher than the guess number
 *                       otherwise return 0
 * var guess = function(num) {}
 */
/**
 * @param {number} n
 * @return {number}
 */
let guessNumber = function(n) {
    const rec = (low, high) => {
        if(low > high){
            return;
        }
       // 1.计算中间元素，分割数组
        const mid = Math.floor((low + high) / 2);
        // 2.与猜测的数字进行比较
        const res = guess(mid);
        // 3.递归地在较大或者较小子数组进行二分搜索
        if(res === 0){
            return mid;
        }else if(res === 1){
            return rec(mid + 1, high);
        }else{
            return rec(low, mid - 1);
        }
    }
    return rec(1, n);
};
复制代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
 var invertTree = function(root) {
    if(!root){
        return null;
    }
    return{
        //1.根节点值不变
        val:root.val,
        //2.递归地将左子树与右子树结点变换
        left:invertTree(root.right),
        //3.递归地将右子树与左子树结点变换
        right:invertTree(root.left)
    }
};
复制代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
let isSameTree = function(p, q) {
    if(!p && !q){
        return true;
    }
    /**
     * 判断条件：
     * 1.p树和q树同时存在；
     * 2.每遍历一个节点，两棵树的节点值都存在；
     * 3.递归左子树，比较每个节点值；
     * 4.递归右子树，比较每个节点值。
     */
    if(p && q && p.val === q.val &&
        isSameTree(p.left, q.left) &&
        isSameTree(p.right, q.right)
    ){
        return true;
    }
    return false;
};
复制代码

let isSymmetric = function(root){
    if(!root){
        return true;
    }
    const isMirror = (l, r) => {
        if(!l && !r){
            return true;
        }
        /**
         * 判断条件：
         * 1.左子树和右子树同时存在；
         * 2.左子树和右子树的根节点相同；
         * 3.左子树的左节点和右子树的右节点镜像相同；
         * 4.左子树的右结点和右子树的左结点镜像相同
         */
        if(l && r && l.val === r.val &&
            isMirror(l.left, r.right) &&
            isMirror(l.right, r.left)
        ){
            return true;
        }
        return false;
    }
    return isMirror(root.left, root.right);
}
复制代码

/*
 * @param {number} n
 * @return {number}
 */
// 数组方法
var climbStairs = function(n) {
    if(n < 2){
        return 1;
    }
     // 记录第0阶和第1阶可以走多少步
    const dp = [1, 1];
    // 从第2阶开始遍历，直至第5阶
    for(let i = 2; i <= n; i++){
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};
复制代码

let climbStairs2 = function(n){
    if(n < 2){
        return 1;
    }
    //定义一个变量，记录 n - 2 时的台阶数
    let dp0 = 1;
    //定义一个变量，记录 n - 1 时的台阶数
    let dp1 = 1;
    for(let i = 2; i <= n; i++){
        const temp = dp0;
        //每遍历一次，就让dp0指向下一个数的值，即dp1
        dp0 = dp1;
        //每遍历一次，就让dp1指向dp1下一个数的值，即前两个数的和，也就是dp1和原来dp0的值
        dp1 = dp1 + temp;
    }
    return dp1;
}
复制代码

/**
 * @param {number[]} nums
 * @return {number}
 */
let rob1 = function(nums) {
    if(nums.length === 0){
        return 0;
    }
    // 前0个房屋和前1个房屋能劫持到的金钱数
    const dp = [0,nums[0]];
    for(let i = 2; i <= nums.length; i++){
        dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
    }
    return dp[nums.length];
};
复制代码

let rob2 = function(nums) {
    if(nums.length === 0){
        return 0;
    }
    let dp0 = 0;
    let dp1 = nums[0];
    for(let i = 2; i <= nums.length; i++){
        const dp2 = Math.max(dp0 + nums[i - 1], dp1);
        dp0 = dp1;
        dp1 = dp2;
    }
    return dp1;
};
复制代码

let uniquePaths = function(m, n){
    const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
    for(let i = 0; i < m; i++){
        // 将第一列全部补上1
        f[i][0] = 1;
    }
    for(let j = 0; j < n; j++){
        // 将第一行全部补上1
        f[0][j] = 1;
    }
    for(let i = 1; i < m; i++){
        for(let j = 1; j < n; j++){
            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    return f[m - 1][n - 1];
}