前言
数据结构与算法属于开发人员的内功，不管前端技术怎么变，框架怎么更新，版本怎么迭代，它终究是不变的内容。 始终记得在参加字节青训营的时候，月影老师说过的一句话，不要问前端学不学算法。计算机学科的每一位都有必要了解算法，有
写出高质量代码的潜意识。
一、递增顺序搜索树
1.1 问题描述
给你一棵二叉搜索树的 root ，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
示例 1：
输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9] 输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
示例 2：
输入：root = [5,1,7] 输出：[1,null,5,null,7]
提示：
- 树中节点数的取值范围是 [1, 100]
- 0 <= Node.val <= 1000
1.2 题解思路
中序遍历直接改变节点的指向，每次创建一个新节点
var increasingBST = function(root) { const dommy = new TreeNode(-1) // 创建一个虚拟节点 let p = dommy const rec = (root)=>{ // 中序遍历 if(!root) return rec(root.left) p.right = new TreeNode(root.val) p = p.right rec(root.right) } rec(root) return dommy.right };
二、 二叉搜索树的后序遍历序列
2.1 问题描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5 / \ 2 6 / \ 1 3
示例 1：
输入: [1,6,3,2,5] 输出: false
示例 2：
输入: [1,3,2,6,5] 输出: true
2.2 题解分析
实现的核心思路第一点: BST后续遍历的结果最后一个是根节点，所有小于根节点的值属于左子树。 ac代码中注释。
2.3 AC代码
var verifyPostorder = function(postorder) { const length = postorder.length if(length<2) return true // 递归终止条件 const root = postorder[length-1] // 根节点 // 值在 [0,root) 之间的属于左子树 值在 (root,+无穷] 属于右子树 let i = 0 // 计算比根节点小的部分 也就是根节点的左边 for(;i<length-1;i++){ if(postorder[i]>root){ break } } // 注意 slice 方法为 左闭右开 let left = postorder.slice(0,i) let right = postorder.slice(i,length-1) let result = left.every(val=>val<root) && right.every(val=>val>root) // 判断左树中的值是否都小于 if(result){ // 递归判断左右子树 是否属于BST return verifyPostorder(left) && verifyPostorder(right) }else{ return false } }
我这糟糕的提交记录呀 ┭┮﹏┭┮
总结
对称性质的算法一共有六个系列
- # 【算法之路】😉 吃透对称性递归 (一)
- # 【算法之路】😎 吃透对称性递归 (二)
- # 【算法之路】😎 吃透对称性递归 (三)
- # 【算法之路】🤦♂️ 吃透对称性递归 (四)
- # 【算法之路】✌ 吃透对称性递归 (五)
- # 【算法之路】📝 吃透对称性递归 (六)
好了，本篇【算法之路】📝 吃透对称性递归 (六)到这里就结束了，我是邵小白，一个在前端领域摸爬滚打的大三学生，欢迎👍评论。
