判断对称二叉树

2021-03-11

二叉树【

每个节点最多有两个子节点。

      10
    /    \
    9    20
        /   \
       15   35

二叉树的特点：

  1. 每个节点最多有两个子树，节点的度最大为2；
  2. 左子树和右子树是有顺序的，次序不能颠倒；
  3. 即使某节点只有一个子树，也要区分左右子树；

对称二叉树

如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

        10
     /      \
    5         5
  /   \      /  \
1      4    4    1

实现思路:

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

模拟一个对称二叉树和非对称二叉树：

//对称二叉树
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 },
  },
};

JS实现

利用递归实现对称二叉树判断

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)); // true
console.log(isSymmetrical(binaryTree)); // false

More

对称二叉树
https://www.luogu.com.cn/problem/P5018

对称二叉树（思路与实现）
https://blog.csdn.net/qq_28081081/article/details/80878973

JavaScript判断对称二叉树
https://blog.csdn.net/AS_Tammy/article/details/93600323