知识点

LeetCode算法

1. LeetCode算法

   1. 199.【二叉树的右视图】

      解题思路：

      BFS解题即可。

   2. 104.【二叉树的最大深度】

      解题思路：

      DFS或者BFS解题。

   3. 101.【对称二叉树】

      解题思路：

      确定好递归函数的定义即可。

   4. 96.【不同的二叉搜索树】

      解题思路：

      首先，为了构建出一棵二叉搜索树，我们可以遍历每个数字 k，将该数字作为树根，将[1..k-1]序列作为左子树，将 [k+1..n]序列作为右子树。

      左子树出来的形态有 a 种，右子树出来的形态有 b 种，则整个树的形态有 a * b 种，因此以 k 为根节点的 BST 种类数 = 左子树 BST 种类数 * 右子树 BST 种类数。

      因此，就是遍历每个数字 k的左子树 BST 种类数 * 右子树 BST 种类数的累加。

      因为子问题独立，并且有重叠子问题，因此使用动态规划完成。

      首先定义dp数组，dp[i] ：用连着的 i 个数，所构建出的 BST 种类数

      其次，确定base case。当只有0个节点时，BST种类数为1，即[];当只有1个节点，BST种类数为1个，即单个节点。

      最后，确定状态转移方程：dp[k] = dp[k - 1] * dp[n - k]