Lstmxx的空间

101. 对称二叉树

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

链接

递归

function isSymmetric(root: TreeNode | null): boolean {
  if (root === null) return true
  return isSameTree(root.left, root.right)
};

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  if (p === null && q === null) return true
  if ((p === null && q !== null) || (p !== null && q === null)) return false
  if (p.val !== q.val) return false 
  return isSameTree(p.left, q.right) && isSameTree(p.right, q.left)
}

迭代

function isSymmetric(root: TreeNode | null): boolean {
  if (root === null) return true
  let nodeList: Array<TreeNode | null> = []
  nodeList.push(root)
  while(nodeList.length > 0) {
    if (nodeList.length === 1) {
      const parent = nodeList.shift()
      nodeList.push(parent.left)
      nodeList.push(parent.right)
    } else {
      const nodeL = nodeList.splice(0)
      const preList = []
      const backList = []
      const len = nodeL.length
      for(let i = 0; i < len / 2;i++) {
        const startNode = nodeL[i]
        const endNode = nodeL[len - i - 1]
        if (startNode === null && endNode === null) continue
        if (
          (startNode === null && endNode !== null) ||
          (startNode !== null && endNode === null) ||
          (startNode.val !== endNode.val)
        ) {
          return false
        }
        preList.push(startNode.left)
        preList.push(startNode.right)
        backList.unshift(endNode.right)
        backList.unshift(endNode.left)
      }
      nodeList = preList.concat(backList)
    }
  }
  return true
}