这个系列没啥花头，就是纯 leetcode 题目拆解分析，不求用骚气的一行或者小众取巧解法，而是用清晰的代码和足够简单的思路帮你理清题意。让你在面试中再也不怕算法笔试。

89. 二叉树展开为链表 (flatten-binary-tree-to-linked-list)

题目

这里不贴题了，leetcode打开就行，题目大意：

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。

展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

输入：root = []
输出：[]
输入：root = [0]
输出：[0]
复制代码

基本思路

这个题目的方式其实也是遍历二叉树的一种类型。

参见二叉树的遍历

还是思考这个问题的最小操作，分解它 !为第一次重点


    1                1              1 
   / \              / \              \
  2!  5     ->     2!  5      ->      2
 / \   \            \   \              \
3!  4!  6            3!  6              3
                      \                  \
                       4!                 4
                                           \
                                            5
                                             \          
                                              6        
复制代码

这个规律还是很好发现的，那么程序怎么写?

我们看出来，一个节点的最小操作其实就是：拉平一个二叉树

左子树变成右子树
原右子树挂到当前右子树的末尾

那么如何按题目要求把一棵树拉平成一条链表

我们首先要把左子树和右子树拉平才行，这样才能继续把这个节点进行拉平，所以第一步是将 root 的左子树和右子树拉平。也就是说这波递归操作在前面。(思考下应该是个后序遍历的框架)
当前节点进行最小操作:
1. 左子树变成右子树
2. 原右子树挂到当前右子树的末尾

写法实现

var flatten = function(root) {
  if (root === null) {
    return null
  }
  // 先进行递归操作，把子树都给拉平了，再操作当前节点(拉平当前节点)
  flatten(root.left)
  flatten(root.right)
  // 此时左右子树已经拉平 (很像图例的第二幅图)
  // 进行最小操作 
  let origin_left = root.left
  let origin_right = root.right

  // 1.左子树变成右子树
  root.left = null
  root.right = origin_left

  // 2. 原右子树挂到当前右子树的末尾
  // 先获取拉平后的最后的节点作为最后的挂载点
  let lastRightNode = root
  while (lastRightNode.right !== null) {
    lastRightNode = lastRightNode.right
  }
  lastRightNode.right = origin_right
};
复制代码

90. 不同的子序列 (distinct-subsequences)

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，”ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
复制代码

其实就是找方案数。

基本思路

看到这种题目一般想到动态规划，找递推公式，其实就是找关系。

对动态规划基本概念不熟悉请移步 DP 基础

基本步骤

我们还是从这三个角度去看问题

寻找最优子结构(状态表示)
归纳状态转移方程(状态计算)
边界初始化

问题本身计算在 s 的子序列中 t 出现的个数。

我们简化问题，其实可以想象这两个字符串短一点，建立两个指针 i, j

状态表示: dp[i][j] 表示 s[0~i) 的子序列与 t[0~j) 出现的个数是子问题，我们分别剪短 s 和 t

例如原 s = "babgbag", t = "bag"
                 i          j    注意 < i,j 前闭后开
那么我们剪短后的 s' = s[0~i) = "babgba"
               t' = t[0~j) = "ba"
其实就是最后一位我们先去掉，这样问题就简化了
原问题的解其实就是  dp[s.length][t.length]
复制代码

那子问题和原问题的关系，其实就是状态转移方程的推理

状态转移方程
- 先思考容易的，如果 s[i] !== t[j]，说明 s 就算减一位，对原问题是不影响的那么 dp[i][j] = dp[i - 1][j] 类似于 s = ‘abcxxxx’ t = ‘abc’，你想就算把 s 后面的 x 都砍掉对原结果是不影响的。
- 然后如果 s[i] === t[j] ，那么就是分这样两种情况，
  - 一种是最后一位是必要位 则 dp[i - 1][j - 1]
  - 最后一位并不必要，也可以直接去掉，因为前面已经组好了 dp[i - 1][j]
- 那么方程就是 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
边界条件
- 我们可以在 dp[i][j]前插入一个空串，表示可以选择空。选择 “” 空，(j = 0) 则 t = ""，则 dp[i][0] = 1 每个子串都是一个解, 因为空字符串是任何字符串的子序列
- 当 i = 0 时，就不可能有解了 dp[0][j] = 0

下面的代码就很清晰了

写法实现

var numDistinct = function(s, t) {
  // 长度宽度 + 1，表示 index = 0 时 选的是空字串
  let [m, n] = [s.length + 1, t.length + 1]
  if (m < n) {
    return 0
  }
  let dp = new Array(m).fill(0).map(
    item => new Array(n).fill(0)
  )
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      // 处理边界，注意顺序，空串是空串的子集，比较特殊
      if (j === 0) {
        dp[i][j] = 1
      } else if (i === 0) {
        dp[i][j] = 0
      } else {
        if (s[i-1] === t[j-1]) {
          dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
        } else {
          dp[i][j] = dp[i-1][j]
        }
      }
    }
  }
  return dp[m - 1][n - 1]
};

let s = "babgbag", t = "bag"
console.log(numDistinct(s, t));
复制代码

另外向大家着重推荐下这位大哥的文章，非常深入浅出，对前端进阶的同学非常有作用，墙裂推荐！！！核心概念和算法拆解系列

今天就到这儿，想跟我一起刷题的小伙伴可以加我微信哦
搜索我的微信号infinity_9368，可以聊天说地
加我暗号 “天王盖地虎” 下一句的英文，验证消息请发给我
presious tower shock the rever monster，我看到就通过，暗号对不上不加哈，加了之后我会尽我所能帮你，但是注意提问方式，建议先看这篇文章：提问的智慧