简介最近换了工作。虽然我已经是大叔级的程序员了，但是三件套还是少不了的：更新简历、刷boss、刷面试题。今年的行情有点冷，前端人又要开始碾压算法了。目前难度以简单为主，少数为中等（大厂较多）。就我而言，三年前我曾经扫描过30个Leetcode，但现在看来数量不够，所以这次我不得不重新捡起来。其中有一个二叉树中等主题。题目不难，但我觉得对我启发很大，尤其是几轮的分析过程。本文将整理自己思路的过程分享一下，希望对大家有所启发。第一轮第一轮主要是看题目：给你一个整数n，有多少棵恰好由n个节点组成且其节点值从1到n不同的二叉搜索树？返回满足题意的二叉搜索树的数量。首先是题目的阅读理解。我不做很多问题。时间长了，二叉查找树的概念有点模糊。先从搜索概念的解释说起：二叉搜索树是一种左子树小于根，右子树大于根的二叉树。结合例子，很容易理解题目的意思：对于给定的数列1-n，可以排序出多少棵二叉搜索树。然后就是分析如何解决这个问题，也就是想办法计算排列数。我很快想到了数学中的排列组合。排列组合可以转化为公式。例如，10个小学生排成一排，有多少种排列？可以转化为式10的阶乘。但是二叉搜索树的排列方式不一样。根节点有n种，但是再往下有几种排列方式。如何计算？我有点不知所措。想了几分钟，还是找不到规律。我要查答案...第二轮第二轮是重点思考安排。第一轮遇到困难，我差点就去查答案，然后被自己压着，静下心来重新整理思路。思考的方向是如何从题目的细节中找到排列规律。首先想到的是二叉搜索树。我们看一下它的概念：左边比根小，右边比根大。这和有序数组不一样同理，选择一个数组元素作为根后，左边的数是左子树，右边的数是右子树。其实实际数组代表的是二叉树，存在于数据结构中，时间太久忘记了。比如（有时举个例子更容易理解），给定n=5，以2为树根，则左子树为1，右子树为3-5，1的排列为1.右子树的3-5个呢，怎么排？好像又卡住了。关键的突破来了。既然是有序数组，那么3-5的排列方式和1-3的排列方式一样吗？uniform减2不影响排序的顺序，所以排序的次数是一样的！那么，不管是什么数，我们都可以抽象成1-n的排列！我们可以使用迭代来解决问题。Aftertheabstractionis:givenasequenceof1-nnumbers,whenanumberk(1≤k≤n)isselectedastheroot,f(k)=f(k-1)*f(n-k).f(1),f(2)可以直接给定。第一版代码来了，但是找到pattern后，没写几行代码，提交后立马pass了。varnumTrees=function(n){//注意：当n=0时，需要将其视为1，因为n=0表示没有子节点，这也是一种安排。如果(n<3)返回n||1让nums=0for(leti=1;i<=n;i++){nums+=numTrees(i-1)*numTrees(n-i)}returnnums};第三轮三轮优化，第二轮思路整理让我终于摸清了解决问题的思路，也给了我很大的信心和启发，但是复杂度比较高，有很大的优化空间。优化思路也是从3-5和1-3的排列入手，不难发现：数组过半后，数组后半部分的排列数其实和上半场！也就是说后半部分不用计算，上半部分加倍即可。唯一需要考虑的是数组的长度要分为奇数和偶数。代码也很简单，贴出来参考一下。varnumTrees=function(n){如果(n<3)返回n||1letnums=0letmid=Math.ceil(n/2)letifor(i=1;i
