前言
数据结构与算法属于开发人员的内功，不管前端技术怎么变，框架怎么更新，版本怎么迭代，它终究是不变的内容。 始终记得在参加字节青训营的时候，月影老师说过的一句话，不要问前端学不学算法。计算机学科的每一位都有必要了解算法，有
写出高质量代码的潜意识。
一、 从二叉搜索树到更大和树
1.1 问题描述
给定一个二叉搜索树 root (BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
提醒一下， 二叉搜索树 满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。
示例 1：
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：
输入：root = [0,null,1] 输出：[1,null,1]
提示：
- 树中的节点数在
[1, 100]范围内。 0 <= Node.val <= 100- 树中的所有值均 不重复 。
2.2 题解思路
本题给的条件是BST，二叉搜索树，我们先回顾一下二叉搜索树的一些特点吧。
- BST的左子节点都小于根节点，右子节点都大于根节点
- BST的中序遍历的结果是递增的 基于上述两个特点，我们不妨按照右->中->左节点的方式去遍历，这样我们得到的结果就是递减的，之前访问的节点值都比当前访问的要大。
这里借用笨猪爆破组的图
- 对于每一个节点都是先去遍历其右子树，再累加给sum
- 再处理当前节点，将sum赋值给当前节点
- 递归处理左子节点
3.3 AC代码
var bstToGst = function(root) { let sum = 0 const inOrder = (root)=>{ if(!root) return inOrder(root.right) // 不断递归直到最右子节点 sum +=root.val root.val = sum inOrder(root.left) } inOrder(root) return root };
二、二叉搜索树中的搜索
2.1 问题描述
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
示例 1:
输入：root = [4,2,7,1,3], val = 2 输出：[2,1,3]
Example 2:
输入：root = [4,2,7,1,3], val = 5 输出：[]
提示：
- 数中节点数在 [1, 5000] 范围内
- 1 <= Node.val <= 107
- root 是二叉搜索树
- 1 <= val <= 107
2.2 题解思路
实现思路：
- 先序遍历查找结果，满足则存入。
- 找到了则无需继续递归。
var searchBST = function(root, val) { let res = null const rec = (root)=>{ if(!root||res) return if(root.val==val){ res = root } rec(root.left) rec(root.right) } rec(root) return res };
优化上述代码: 既然是BST，那么我们可以在当前节点小于val的时候递归左节点，大于的时候递归右节点 实践复杂度O(logN)
var searchBST = function(root, val) { let res = null const rec = (root)=>{ if(!root||res) return if(root.val==val){ res = root }else if(root.val>val){ rec(root.left) }else{ rec(root.right) } } rec(root) return res };
总结
对称性质的算法一共有六个系列
- # 【算法之路】😉 吃透对称性递归 (一)
- # 【算法之路】😎 吃透对称性递归 (二)
- # 【算法之路】😎 吃透对称性递归 (三)
- # 【算法之路】🤦♂️ 吃透对称性递归 (四)
- # 【算法之路】✌ 吃透对称性递归 (五)
- # 【算法之路】📝 吃透对称性递归 (六)好了，本篇
【算法之路】🤦♂️ 吃透对称性递归 (四)到这里就结束了，我是邵小白，一个在前端领域摸爬滚打的大三学生，欢迎👍评论。
