Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7]

  3
 / \
9  20
  /  \
 15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
  var maxn = -1;
  var ans = [];

  dfs(root, 0);

  function dfs(node, step) {
    if (!node)
      return;

    maxn = step > maxn ? step : maxn;

    if (!ans[step])
      ans[step] = [];

    ans[step].push(node.val);

    dfs(node.left, step + 1);
    dfs(node.right, step + 1);
  }

  for (var i = 0; i <= maxn; i++)
    (i & 1) && (ans[i].reverse());

  return ans;
};

Binary Watch

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

• The order of output does not matter.
• The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
• The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

/**
 * @param {number} num
 * @return {string[]}
 */
var readBinaryWatch = function(num) {
  let hours = [1, 2, 4, 8];
  let minutes = [1, 2, 4, 8, 16, 32];
  let ans = [];

  dfs(num, 0, 0, 0, 0);

  function dfs(left, a, b, hoursTotal, minutesTotal) {
    if (hoursTotal >= 12 || minutesTotal >= 60)
      return;

    if (left === 0) {
      let str = hoursTotal + ":";
      str += minutesTotal < 10 ? '0' + minutesTotal : minutesTotal;
      ans.push(str);
      return;
    }

    // add i to hour
    for (let i = a; i < 4; i++) {
      dfs(left - 1, i + 1, b, hoursTotal + hours[i], minutesTotal);
    }

    // add i to minute
    for (let i = b; i < 6; i++) {
      dfs(left - 1, a, i + 1, hoursTotal, minutesTotal + minutes[i]);
    }
  }

  return Array.from(new Set(ans));
};

Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */

function getBitNum(a, pos) {
  a++;
  var res = Math.pow(2, pos)
    , loop = ~~(a / res)
    , num = loop * (res / 2) + Math.max(a % res - res / 2, 0);
  return num;
}

var rangeBitwiseAnd = function(m, n) {
  var ans = 0
    , tmp = n
    , digits = 0;

  while (tmp) {
    digits++;
    tmp >>= 1;
  }

  for (var i = 0; i < digits; i++) {
    var num = getBitNum(n, i + 1) - getBitNum(m - 1, i + 1);
    if (num === n - m + 1)
      ans += Math.pow(2, i);
  }

  return ans;
};