1.构建乘积数组：

给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]A[i+1]...*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）
对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。

分析：将B[ i ]分成两部分，
分别是左半部分：C[ i ] = A[ 0 ] * A[ 1 ] * ... * A[ i - 1 ]，
和右半部分：D[ i ] = A[ i + 1 ] * A[ i + 2 ] * ... * A[ n - 1 ]。
第一次for循环，将B [ i ]装入左半部分，第二次for循环再装入右半部分。

图解

function multiply(array)
{
    // write code here
    let b = []
    let n = array.length
    b[0] = 1
    for (let i = 1 ; i < n ; ++i) {
        b[i] = b[i - 1] * array[i -1]
    }
    
    for (let i = n - 1, temp = 1 ; i >= 0  ;i--){
        b[i] = b[i] * temp
        temp = temp * array[i]
    }
    return b
}

---

2. 不用加减乘除做加法：

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

分析：
解法1：用i++和i--

function Add(num1, num2)
{
    let res = num1
    if (num2 == 0) {return res}
    // write code here
    for (let i = num2 ; i != 0 ; i > 0 ? i-- : i++) {
        i > 0 ? res++ : res--
    }
 
    return res
}

解法2：用二进制运算

function Add(num1, num2)
{
        let result = 0;
        let carry = 0;
        do{
            result = num1 ^ num2;       //不带进位的加法
            carry = (num1 & num2) << 1; //进位
            num1 = result; 
            num2 = carry;  
        }while(carry != 0); // 进位不为0则继续执行加法处理进位
        return result;
 
}

---

3. 用两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

• 用两个栈来存储入队列和出队列，当入队列时，数据压入stack1，当需要出队列时，将stack1压入stack2再出栈，即可达到先入先出。

• 需要注意的是，当stack2没有数字时，需要将stack1的数据压入stack2，而当stack2已经有数据时，要先将stack2的数据全部出栈后才能再进行数据转移。

  
  入栈stack1

转移到stack2 当stack2没出栈完时

const inStack = []
const outStack = []

function push(node)
{
    // write code here
    inStack.push(node)
}
function pop()
{
    // write code here
    if (outStack.length == 0) {
        while (inStack.length) {
            outStack.push(inStack.pop())
        }
        return outStack.pop()
    } else {
        return outStack.pop()
    }
}

4. 变态阶梯跳

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析：数学归纳法，从n阶往下跳一次有n种跳法（跳到0到n-1阶），从n-1阶往下跳一次有n-1种跳法（跳到0到n-2阶），……，从1阶往下跳只有1种跳法，所以，从n阶往下跳一共有1+2+(1+2)+(1+2+(1+2))+...+(1+2+(1+2)+...+(1+...+(1+...+)))

• 在第1阶，有1种跳法
• 在第2阶，有2种跳法
• 在第3阶，有1+在第1阶+第2阶，加起来所有的跳法，即（1+1+2）= 4
• 在第4阶，有1+在第1阶+第2阶+第3阶，加起来所有的跳法，即1+（ 1 + 2 +（ 1+1+2））= 8
• ...
• 在第n阶，有1+在第1阶+第2阶+第3阶+...+第n-1阶，加起来所有的跳法，有2*（n-1）种跳法

function jumpFloorII(number)
{
    // write code here\
    if (number == 0) {return 0 }
    return Math.pow(2,number -1)
}

---

5. 二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。

镜像二叉树

function Mirror(root)
{
    // write code here
    if (root == null) {
        return
    }
    let temp = root.left
    root.left = root.right
    root.right = temp
    Mirror(root.left)
    Mirror(root.right)
}

---

6. 二叉树的深度

题目描述：
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
leetcode优秀回答（带图文）：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/solution/mian-shi-ti-55-i-er-cha-shu-de-shen-du-xian-xu-bia/

方法1：递归法

function TreeDepth(pRoot)
{
    // write code here
    if ( pRoot == null ) {
        return 0
    } else {
        return 1 + Math.max( TreeDepth (pRoot.left) , TreeDepth(pRoot.right) )
    }
}

方法2：利用队列，count是当前的节点，nextcount是当前深度总的节点。【总是要遍历到当前深度的最后一个节点，深度才加1】

function TreeDepth(pRoot)
{
      if(pRoot == null){return 0;}
          
      var queue = new Array()
      queue.unshift(pRoot);
      let depth = 0;
      //用size控制high增长的次数和时机(同一层的元素没有完全退出队列的时候high不可以增加)
      let size = 0;
      while(queue.length != 0){
          size = queue.length;//队列长度
          while(size != 0){
              let node = queue.pop();
              if(node.left != null){
                  queue.unshift(node.left);
              }
              if(node.right != null){
                  queue.unshift(node.right);
              }
              size--;//当size==0时说明同一层的元素遍历完成
          }
          depth++;
      }
      return depth;
  }
}