这个系列没啥花头，就是纯 leetcode 题目拆解分析，不求用骚气的一行或者小众取巧解法，而是用清晰的代码和足够简单的思路帮你理清题意。让你在面试中再也不怕算法笔试。

76. 相同的树 (validate-binary-search-tree)

题目

这里不贴题了，leetcode打开就行，题目大意：

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

输入：p = [1,2,3], q = [1,2,3]
输出：true
复制代码

基本思路

这题没啥好说，二叉树递归遍历比较就行。

写法实现

var isSameTree = function(p, q) {
  // 都是空相等
  if (p === null && q === null) {
    return true
  } else if (p !== null && q !== null) {
    if (p.val !== q.val) {
      return false
    } else {
      // 递归比较左右子树
      return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    }
  } else {
    // 这是一个 null 一个 非 null 的分支
    return false
  }
};
复制代码

77. 对称二叉树 (symmetric-tree)

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
复制代码

基本思路

跟上题相同都是关于二叉树的遍历问题，我们想大致了解下

这篇写的非常清楚，[算法拆解] 一文说透二叉树的遍历套路

我们平时还要多注意培养几个重要技能：拆解问题 和 转化问题（数学上称换元）

这题是检查一棵树是否是镜像对称那么我们可以换元为：这棵树翻转后和他本身一样。

那么问题就拆解为

翻转二叉树
判断两个二叉树(原树 & 翻转树)是否相等(就是上面一题)

这是一种思路

另外就是和上面判断相等类似，直接去逻辑分析。

还是去递归判断左右子树是否对称
出口就是用 null 来判断

写法实现

先实现下翻转二叉树, 引用下上面文章中方法

const invertTree = (root) => {
  if (root === null) {
    return null;
  }
  
  // 先访问的是根 就在这里进行交换左右子树操作就行
  // 这里用的是解构赋值 不知道可以查查 ES6解构赋值
  [root.left, root.right] = [root.right, root.left]
  
  // 然后遍历左子树
  invertTree(root.left)         // ---------> (左)
  // 再遍历右子树
  invertTree(root.right)        // ---------> (右)
  
  return root
}
复制代码

组合判断是否相等我就不写了，非常简单，下面实现第二种思路。

var isSymmetric = function(root) {
  const isMirror = (tree1, tree2) => {
    // 递归出口
    if (tree1 === null && tree2 === null) {
      return true
    }
    // 由于上面已经排除两个都是 null 下面就是 1个为空 那肯定不对称
    if (tree1 === null || tree2 === null) {
      return false
    }
    // 那么就判断是否对称，先根，再递归的去判断左右子树
    // 根对称，以及左右子树的对应节点对称就返回 true
    if (tree1.val === tree2.val 
      && isMirror(tree1.left, tree2.right) 
      && isMirror(tree1.right, tree2.left)) {
      return true
    } else {
      return false
    }
  }
  return isMirror(root, root)
};
复制代码

另外向大家着重推荐下这位大哥的文章，非常深入浅出，对前端进阶的同学非常有作用，墙裂推荐！！！核心概念和算法拆解系列

今天就到这儿，想跟我一起刷题的小伙伴可以加我微信哦
搜索我的微信号infinity_9368，可以聊天说地
加我暗号 “天王盖地虎” 下一句的英文，验证消息请发给我
presious tower shock the rever monster，我看到就通过，暗号对不上不加哈，加了之后我会尽我所能帮你，但是注意提问方式，建议先看这篇文章：提问的智慧