递归的实现和特性

树的面试题解法一般都是递归。主要原因如下：

• 节点的定义，本身就是以递归的方式进行的
• 树、二叉树、搜索二叉树，存在重复性。

递归（Recursion），本质就是通过函数体来进行的循环。

递归模板

function recursion (level, param1, param2, ...):
	// 1. recursion terminator	递归终结条件
  if level > MAX_LEVEL:
  	process_result
    return
               
  // 2. process logic in current level	处理当前层逻辑
  process(level, data...)

  // 3. drill down	下探到下一层
  recursion(level + 1, p1, ...)
                 
  // 4. reverse the current level staus if needed	清理当前层

注意点：

• 不要人肉递归（画递归树）
• 找到最近最简方法，将其拆解成可重复解决的问题（最近重复子问题）
• 数学归纳法思维

爬楼梯（阿里巴巴、腾讯、字节跳动在半年内面试常考）

括号生成 (字节跳动在半年内面试中考过)

翻转二叉树 (谷歌、字节跳动、Facebook 在半年内面试中考过)

验证二叉搜索树（亚马逊、微软、Facebook 在半年内面试中考过）

二叉树的最大深度（亚马逊、微软、字节跳动在半年内面试中考过）

二叉树的最小深度（Facebook、字节跳动、谷歌在半年内面试中考过）

二叉树的序列化与反序列化（Facebook、亚马逊在半年内面试常考）

// 爬楼梯 

// f(n) = f(n - 1) + f(n - 2)，mutual exclusive、complete exhaustive

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
  if (n <= 2) return n;

  let n1 = 1,
      n2 = 2;
    
  for (let i = 2; i < n; i++) {
    const n3 = n1 + n2;

    n1 = n2;
    n2 = n3;
  }

  return n2;
};

// 括号生成

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
  const ret = [];

  function _generate (left, right, n, s) {
    if (left === n && right === n) {
      ret.push(s);
      return;
    }

    if (left < n) {
      _generate(left + 1, right, n, s + '(');
    }
    if (left > right) {
      _generate(left, right + 1, n, s + ')');
    }
  }

  _generate (0, 0, n, '');

  return ret;
};

// 翻转二叉树

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
  let curr;

  const preorder = (root) => {
    if (!root) return;

    curr = root.left;
    root.left = root.right;
    root.right = curr;

    preorder(root.left);
    preorder(root.right);
  }

  preorder(root);

  curr = null;

  return root;
};

// 验证二叉搜索树

// BST - 中序遍历是递增的，有序的

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
  const inorder = (root, min = -Infinity, max = Infinity) => {
    if (!root) return true;

    if (root.val <= min || root.val >= max) return false;

    return (
      inorder(root.left, min, root.val) && 
      inorder(root.right, root.val, max)
    )
  }

  return inorder(root);
};

// 二叉树的最大深度

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
  if (!root) return 0;

  let deep = 0;

  const queue = [[root, 1]];

  while (queue.length) {
    const [ root, l ] = queue.shift();

    deep = Math.max(deep, l);

    root.left && queue.push([ root.left, l + 1 ]);
    root.right && queue.push([ root.right, l + 1 ]);
  }

  return deep;
};

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
  if (!root) return 0;

  let deep = 1;

  const dfs = (root, l) => {
    if (!root) return;

    deep = Math.max(l, deep);

    root.left && dfs(root.left, l + 1);
    root.right && dfs(root.right, l + 1);
  }

  dfs(root, 1);

  return deep;
};

// 二叉树的最小深度

/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
  if (!root) return 0;

  const queue = [[ root, 1 ]];

  while (queue.length) {
    const [root, l] = queue.shift();

    if (!root.left && !root.right) {
      return l;
    }

    root.left && queue.push([ root.left, l + 1 ]);
    root.right && queue.push([ root.right, l + 1 ]);
  }
};

/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
  if (!root) return 0;

  let deep = 0;

  const dfs = (root, l) => {
    if (!root.left && !root.right) {
      // 首次赋值，必须是真实深度，不能给 deep 赋值默认值
      deep = deep ? Math.min(deep, l) : l;
    }

    root.left && dfs(root.left, l + 1);
    root.right && dfs(root.right, l + 1);
  }

  dfs(root, 1);

  return deep;
};

// 二叉树的序列化和反序列化

// 深度优先遍历
/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
  const dfs = (root) => {
    if (!root) return '*';

    const left = dfs(root.left),
          right = dfs(root.right);
    
    return `${ root.val },${ left },${ right }`;
  }

  return dfs(root);
};
/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
  const list = data.split(',');

  const dfs = (list) => {
    const rootVal = list.shift();

    if (rootVal == '*') {
      return null;
    }

    const root = new TreeNode(rootVal);

    root.left = dfs(list);
    root.right = dfs(list);

    return root;
  }

  return dfs(list);
};


// 广度优先遍历
/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
  const queue = [root];

  const ret = [];

  while (queue.length) {
    const root = queue.shift();

    if (root) {
      ret.push(root.val);
      queue.push(root.left);
      queue.push(root.right);
    } else {
      ret.push('*')
    }
  }

  return ret.join(',');
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
  if (data == '*') return null;

  const list = data.split(',');

  const root = new TreeNode(list[0]);
  const queue = [root];

  let cursor = 1;

  while (cursor < list.length) {
    const root = queue.shift();

    const leftVal = list[cursor],
          rightVal = list[cursor + 1];

    if (leftVal != '*') {
      const leftNode = new TreeNode(leftVal);

      root.left = leftNode;

      queue.push(leftNode);
    }
    if (rightVal != '*') {
      const rightNode = new TreeNode(rightVal);

      root.right = rightNode;

      queue.push(rightNode);
    }

    cursor += 2;
  }

  return root;
};

二叉树的最近公共祖先（Facebook 在半年内面试常考）

从前序与中序遍历序列构造二叉树（字节跳动、亚马逊、微软在半年内面试中考过）

组合（微软、亚马逊、谷歌在半年内面试中考过）

全排列（字节跳动在半年内面试常考）

全排列 II （亚马逊、字节跳动、Facebook 在半年内面试中考过）

// 二叉树的最近公共祖先

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
  const dfs = (root, p, q) => {
    if (!root || root == p || root == q) return root;

    const left = dfs(root.left, p, q),
          right = dfs(root.right, p, q);

    if (!left) return right;
    if (!right) return left;

    return root;
  }

  return dfs(root, p, q);
};

// 前序遍历与中序遍历序列构造二叉树

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
  const map = new Map();

  for (let i = 0; i < inorder.length; i++) {
    map.set(inorder[i], i);
  }

  return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length, map);
};

function buildTreeHelper (preorder, p_start, p_end, inorder, i_start, i_end, map) {
  if (p_start == p_end) {
    return null;
  }

  const root_val = preorder[p_start],
        root_idx = map.get(root_val),
        left_idx = root_idx - i_start;

  const root = new TreeNode(root_val);

  root.left = buildTreeHelper(preorder, p_start + 1, p_start + left_idx + 1, inorder, i_start, root_idx, map);
  root.right = buildTreeHelper(preorder, p_start + left_idx + 1, p_end, inorder, root_idx + 1, i_end, map);

  return root;
}

// 组合

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
  const ret = [];

  const dfs = (cur, n, k, temp) => {
    if (temp.length + (n - cur + 1) < k) return;

    if (temp.length == k) {
      return ret.push(temp);
    }

    dfs(cur + 1, n, k, [...temp, cur]);
    dfs(cur + 1, n, k, temp);
  }

  dfs(1, n, k, []);

  return ret;
};

// 全排列

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
  const ret = [];

  const backtrack = (path) => {
    if (path.length === nums.length) {
      return ret.push(path);
    }

    nums.forEach(n => {
      if (path.includes(n)) return;
      backtrack(path.concat(n));
    });
  }

  backtrack([]);

  return ret;
};

// 全排列 II

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
  const ret = [];

  const visited = new Array(nums.length).fill(false);

  const backtrack = (idx, path) => {
    if (path.length === nums.length) {
      return ret.push(path.slice());
    }

    for (let i = 0; i < nums.length; i++) {
      if (visited[i] || (i > 0 && nums[i] === nums[i - 1] && !visited[i - 1])) continue;

      path.push(nums[i]);

      visited[i] = true;

      backtrack(idx + 1, path);

      visited[i] = false;

      path.pop();
    }
  }

  nums.sort((x, y) => x - y);

  backtrack(0, []);

  return ret;
};