前言
数据结构与算法属于开发人员的内功，不管前端技术怎么变，框架怎么更新，版本怎么迭代，它终究是不变的内容。 始终记得在参加字节青训营的时候，月影老师说过的一句话，不要问前端学不学算法。计算机学科的每一位都有必要了解算法，有
写出高质量代码的潜意识。
一、相同的树
1.1 题目描述
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3] 输出：true
示例 2：
输入：p = [1,2], q = [1,null,2] 输出：false
示例 3：
输入：p = [1,2,1], q = [1,1,2] 输出：false
1.2 算法思路
对于二叉树的问题，优先想到递归问题，这个问题我们的解法步骤如下：
- 递归实现，如果两个节点的值都是空返回true
- 一个为空一个不为空返回false
- 两个值相同则继续递归两棵树的左节点和右节点，不相同则返回true
1.3 AC代码
var isSameTree = function(p, q) { const dfs = (l,r)=>{ // 左树 和 右树 是否相等 console.log(l,r) if(l===null&&r==null) return true if(l==null || r==null) return false if(l.val!=r.val) return false return dfs(l.left,r.left) && dfs(l.right,r.right) } return dfs(p,q) };
二、翻转二叉树
2.1 题目描述
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3] 输出：[2,3,1]
示例 3：
输入：root = [] 输出：[]
2.2 解决思路
想要翻转一整颗树，其实看到这道问题的时候潜意识的就会想到一个递归模型，本质上就是不断的去递归翻转一个树，我们先想好如何翻转一棵小树
很简单，我们只需要将其左右节点互换即可，那如果翻转一整颗树的话，我们就使用递归去实现就好了，不断去翻转其子树。
const reverseTree = (root) =>{ if(!root) return null return { val: root.val, left: root.right, right: root.left } }
2.3 AC代码
var invertTree = function(root) { if(!root) return null return { val:root.val, left:invertTree(root.right), right:invertTree(root.left) } }
三、N叉树的后序遍历
3.1 问题描述
给定一个 n 叉树的根节点 root ，返回 其节点值的 后序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6] 输出：[5,6,3,2,4,1]
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]
提示：
- 节点总数在范围 [0, 104] 内
- 0 <= Node.val <= 104
- n 叉树的高度小于或等于 1000
3.2 题解分析
如果是二叉树的后续遍历相比各位同学就熟悉的不能再熟悉了，这里是N叉树的后序遍历，实现思路也大同小异，我们先简单看一下N叉树的定义
* function Node(val,children) { * this.val = val; * this.children = children; * };
那不就好办了嘛？ 一层for循环嵌套拿下 子节点
3.3 AC代码
var postorder = function(root) { const res = [] const rec = (root)=>{ if(!root) return // 递归终止条件 for(const child of root.children){ rec(child) } res.push(root.val) } rec(root) return res };
四、二叉树的锯齿层序遍历
4.1 问题描述
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[20,9],[15,7]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
4.2 问题分析
先摆开题目的要求，如果是非锯齿形状的打印我们该怎么做？ 很简单，使用一个index值来记录层级即可，实现的代码如下
var zigzagLevelOrder = 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 };
但是题目要求的是锯齿形状的，有了上面的 从左到右的实现思路，我们只需要加一个判断条件，从index的奇偶性来判断本层结果是从左往右还是从右往左了
4.3 AC代码
var zigzagLevelOrder = function(root) { const res = [] const rec = (root,index)=>{ if(!root) return if(!res[index]){ res[index] = [] } if(index%2==0){ // 0 2 4 从左往右 res[index].push(root.val) }else{ // 1 3 5 从右往左 res[index].unshift(root.val) } rec(root.left,index+1) rec(root.right,index+1) } rec(root,0) return res };
总结
- 对于对称性质的递归，一般都是二叉树和N叉树问题，我们的解题步骤应该是从点到面的。
- 先想好一个子树如何去实现，或者非特殊情况如何去实现。
- 写完框架之后，再去想如何优化或者完善代码，如何从一棵子树通过递归的方式扩展到整颗树。
后续
对称性质的算法一共有六个系列
- # 【算法之路】😉 吃透对称性递归 (一)
- # 【算法之路】😎 吃透对称性递归 (二)
- # 【算法之路】😎 吃透对称性递归 (三)
- # 【算法之路】🤦♂️ 吃透对称性递归 (四)
- # 【算法之路】✌ 吃透对称性递归 (五)
- # 【算法之路】📝 吃透对称性递归 (六)
好了，本篇【算法之路】😉 吃透对称性递归(一)到这里就结束了，我是邵小白，一个在前端领域摸爬滚打的大三学生，欢迎👍评论。
