【算法之路】? 吃透对称性递归 (一)-一一网

Offer 驾到，掘友接招！我正在参与2022春招系列活动-刷题打卡任务，点击查看活动详情。

前言

数据结构与算法属于开发人员的内功，不管前端技术怎么变，框架怎么更新，版本怎么迭代，它终究是不变的内容。 始终记得在参加字节青训营的时候，月影老师说过的一句话，不要问前端学不学算法。计算机学科的每一位都有必要了解算法，有写出高质量代码的潜意识。

一、相同的树

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
};
复制代码