Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

  3
 / \
9  20
  /  \
 15   7

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

      1
     / \
    2   2
   / \
  3   3
 / \
4   4

Return false.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */

var ans;

function dfs(root) {
  if (!root) return;
  
  var a = root.left ? dfs(root.left) : 0
    , b = root.right ? dfs(root.right) : 0;

  if (Math.abs(a - b) > 1) {
    ans = false;
  }

  return Math.max(a, b) + 1;
}

var isBalanced = function(root) {
  ans = true;
  dfs(root);
  return ans;
};

Base 7

Given an integer, return its base 7 string representation.

Example 1:

Input: 100
Output: "202"

Example 2:

Input: -7
Output: "-10"

Note: The input will be in range of [-1e7, 1e7].

/**
 * @param {number} num
 * @return {string}
 */
var convertToBase7 = function(num) {
  if (num === 0)
    return '0';
  
  let prefix = num < 0 ? '-' : ''
    , res = []
    , base = 7;

  num = Math.abs(num);

  while (num) {
    res.push(num % base);
    num = ~~(num / base);
  }

  return prefix + res.reverse().join('');
};

Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function(s) {
  s = s.replace(/\s/g, '');
  var numStack = [];
  var symStack = [];
  var len = s.length;
  var num = 0;

  for (var i = 0; i < len; i++) {
    var item = s[i];
    if ('-+('.indexOf(item) !== -1) {
      symStack.push(item);

      if (i && '0123456789'.indexOf(s[i - 1]) !== -1) {
        numStack.push(num);
        num = 0;
      }
    } else if (item === ')') {
      if (i && '0123456789'.indexOf(s[i - 1]) !== -1) {
        numStack.push(num);
        num = 0;
      }

      var _numStack = [];
      var _symStack = [];

      while (true) {
        var sym = symStack.pop();
        if (sym === '(') {
          _numStack.unshift(numStack.pop());
          numStack.push(help(_numStack, _symStack));
          break;
        }

        _numStack.unshift(numStack.pop());
        _symStack.unshift(sym);
      }
    } else {
      num = num * 10 + (+item);
    }
  }

  if (s[len - 1] !== ')')
    numStack.push(num);

  return help(numStack, symStack);
};


/**
 * @param  {array} numStack
 * @param  {array} symStack
 * @return {number}
 */
function help(numStack, symStack) {
  while (numStack.length !== 1) {
    var sym = symStack.shift();
    var a = numStack.shift();
    var b = numStack.shift();

    if (sym === '+')
      numStack.unshift(a + b);
    else
      numStack.unshift(a - b);
  }

  return numStack[0];
}

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function(s) {
  var ans = 0;
  var num = 0;  // single number
  var sign = 1;
  var numStack = [];
  var symStack = [];

  for (var i = 0, len = s.length; i < len; i++) {
    var item = s[i];

    if ('0123456789'.indexOf(item) !== -1) {
      num = num * 10 + (+item);
    } else {
      ans += sign * num;
      num = 0;
      if (item === '+')
        sign = 1;
      else if (item === '-')
        sign = -1;
      else if (item === '(') {
        numStack.push(ans);
        symStack.push(sign);
        ans = 0;
        sign = 1;
      } else if (item === ')') {
        ans = symStack.pop() * ans + numStack.pop();
      }
    }
  }

  ans += sign * num;
  return ans;
};