101、对称二叉树

;(function () {
  /**
   * 101. 对称二叉树
   * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
   *
   * 输入：root = [1,2,2,3,4,4,3]
   * 输出：true
   *
   * 输入：root = [1,2,2,null,3,null,3]
   * 输出：false
   *
   * 进阶：你可以运用递归和迭代两种方法解决这个问题吗？
   *
   */

  // type treeType = TreeNode | null;
  class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
      this.val = val === undefined ? 0 : val
      this.left = left === undefined ? null : left
      this.right = right === undefined ? null : right
    }
  }
  function isSymmetric(root: TreeNode | null): boolean {
    // 方法一：
    let res: (number | null)[][] = []
    let index = 0
    let bool = true
    function preorder(root: TreeNode | null, index: number) {
      !res[index] ? (res[index] = []) : null
      if (!root) {
        res[index].push(null)
        return
      }
      res[index].push(root.val)
      let k = ++index
      preorder(root.left, k)
      preorder(root.right, k)
    }
    preorder(root, index)
    // 遍历二维数组，每一项是否左右对称
    res.forEach((i) => {
      i.forEach((item, index) => {
        let mid = Math.ceil(i.length / 2)
        if (index < mid) {
          i[index] !== i[i.length - 1 - index] ? (bool = false) : null
        }
      })
    })
    return bool

    // 方法二：
    const check = (p: TreeNode | null, q: TreeNode | null): boolean => {
      if (!p && !q) return true
      if (!p || !q) return false
      return p.val === q.val && check(p.left, q.right) && check(p.right, q.left)
    }
    return check(root, root)

    // 方法三：
  }
})()