前言
数据结构与算法属于开发人员的内功，不管前端技术怎么变，框架怎么更新，版本怎么迭代，它终究是不变的内容。 始终记得在参加字节青训营的时候，月影老师说过的一句话，不要问前端学不学算法。计算机学科的每一位都有必要了解算法，有
写出高质量代码的潜意识。
通过本系类的文章带你 穆萨二叉树的对称性问题，废话不多说，直接开始吧 ！ 🙋
一、二叉搜索树中第K小的元素
1.1 问题描述
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
示例 1：
输入：root = [3,1,4,null,2], k = 1 输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3 输出：3
1.2 题解思路
重点观察本题的要求是二叉搜索树,先简单回顾一下二叉搜索树的一些特点吧。
- 根节点的左节点小于根节点
- 根结点的右节点大于根节点 那根据这个要求我们很快就可以想到一个解：
通过中序遍历将结果都存放在一个结果集中，结果集一定是从小到大排列，那么我们只需要打印第k个元素就可以了。
1.3 AC代码
var kthSmallest = function(root, k) { const res = [] const dfs = (root)=>{ if(!root) return dfs(root.left) res.push(root.val) // 注意中序遍历 dfs(root.right) } dfs(root) return res[k-1] // k 从 1开始计数 };
进一步优化,那么当res结果集的长度已经够k了是不是可以停止递归了。
var kthSmallest = function(root, k) { const res = [] const dfs = (root)=>{ if(!root) return if(res.length>=k) return dfs(root.left) res.push(root.val) dfs(root.right) } dfs(root) return res[k-1] };
还能继续优化嘛？ 上述解法的空间复杂度都是O(N), 既然是需要打印结果集中的第k个元素，为什么我们不直接使用一个count来计数，如果当有效的节点递归次数到底了k，我们直接就返回结果就行了。
var kthSmallest = function(root, k) { let count = 0 let res = 0 const dfs = (root)=>{ if(root&&count<=k){ dfs(root.left) if(++count==k){ res = root.val } dfs(root.right) } } dfs(root) return res };
二、二叉树的层序遍历
2.1 问题描述
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
2.2 题解思路
关于树的层级问题解法都很一致，无论是锯齿状还是一直保存从左往右，我们只需要使用index值来记录即可。
2.3 AC代码
var levelOrder = function(root) { const res = [] const rec = (root,index)=>{ if(!root) return if(!res[index]){ res[index] = [] } res[index].push(root.val) rec(root.left,index+1) rec(root.right,index+1) } rec(root,0) return res };
三、二叉树的右视图
3.1 题目描述
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4] 输出: [1,3,4]
示例 2:
输入: [1,null,3] 输出: [1,3]
示例 3:
输入: [] 输出: []
3.2 题解思路
这道题和上一题很类似，其实就是一个层序遍历问题，这次的层序层级变成了，从右往左计算。而且每一层只计算一次，所以我们的做法也很简单，使用一个数组来记录，看看每一个层级是否已经存在了值，如果存在了就无需存入。
3.3 AC代码
var rightSideView = function(root) { const res = [] const rec = (root,index)=>{ if(!root) return if(!res[index]){ res.push(root.val) } rec(root.right,index+1) rec(root.left,index+1) } rec(root,0) return res };
四、二叉树的最大深度
4.1 题目描述
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。
4.2 题解思路
如果上面两个题都做出来了，这个问题就非常简单了，只需要记录层级的最大值即可。
4.3 AC代码
var maxDepth = function(root) { let max = 0 const rec = (root,index)=>{ if(!root) return max = index > max ? index : max // 执行速度快于 Math.max() rec(root.left,index+1) rec(root.right,index+1) } rec(root,1) return max }
后续
对称性质的算法一共有六个系列
- # 【算法之路】😉 吃透对称性递归 (一)
- # 【算法之路】😎 吃透对称性递归 (二)
- # 【算法之路】😎 吃透对称性递归 (三)
- # 【算法之路】🤦♂️ 吃透对称性递归 (四)
- # 【算法之路】✌ 吃透对称性递归 (五)
- # 【算法之路】📝 吃透对称性递归 (六)
好了，本篇【算法之路】😉 吃透对称性递归 (二)到这里就结束了，我是邵小白，一个在前端领域摸爬滚打的大三学生，欢迎👍评论。
