JavaScript判断对称二叉树

参考自 ConardLi：《对称的二叉树》公众号：code 秘密花园

对称二叉树:

           8
          / \
         6   6
        /\   /\
       5  7 7  5

非对称二叉树:

           8
          / \
         6   5
        /\   /\
       5  7 7  5
   

实现思路:

1. 判断根节点相同
2. 左子树的右节点和右子树的左节点相同
3. 右子树的左节点和左子树的右节点相同

步骤 1: 模拟一个对称二叉树和非对称二叉树

// 对称二叉树
const symmetricalTree = {
  val: 8,
  left: {
    val: 6,
    left: {val: 5, left: null, right: null},
    right: {val: 7, left: null, right: null}
  },
  right: {
    val: 6,
    left: {val: 7, left: null, right: null},
    right: {val: 5, left: null, right: null}
  }
}

// 非对称二叉树
const binaryTree = {
  val: 8,
  left: {
    val: 6,
    left: {val: 5, left: null, right: null},
    right: {val: 7, left: null, right: null}
  },
  right: {
    val: 9,
    left: {val: 7, left: null, right: null},
    right: {val: 5, left: null, right: null}
  }
}

步骤 2: 利用递归实现对称二叉树判断

function isSymmetrical(pRoot) {return isSymmetricalTree(pRoot, pRoot);
}

function isSymmetricalTree(node1, node2) {
  // 判断两个节点都是否为空
  if (!node1 && !node2) {return true;}
  // 判断两个节点是否存在一个为空
  if (!node1 || !node2) {return false;}
  // 判断两个节点是否相同
  if (node1.val != node2.val) {return false;}
  return isSymmetricalTree(node1.left, node2.right) && isSymmetricalTree(node1.right, node2.left);
}

输出:

console.log(isSymmetrical(symmetricalTree));
console.log(isSymmetrical(binaryTree));

结果如下:

true
false

参考自 ConardLi：《对称的二叉树》公众号：code 秘密花园