JavaScript判断对称二叉树

iliyaku 发布于2019-08-23 18:17 / 1414人阅读

摘要：参考自对称的二叉树公众号秘密花园对称二叉树非对称二叉树实现思路判断根节点相同左子树的右节点和右子树的左节点相同右子树的左节点和左子树的右节点相同步骤模拟一个对称二叉树和非对称二叉树对称二叉树非对称二叉树步骤利用递归实现对称二叉树判断判断两个

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

对称二叉树:

非对称二叉树:

实现思路:

判断根节点相同

左子树的右节点和右子树的左节点相同

右子树的左节点和左子树的右节点相同

步骤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秘密花园

云服务器 GPU云服务器二叉树 python二叉树平衡二叉树实现二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/104980.html

使用JavaScript完成二叉树的一些基本操作

摘要：另外，由于篇幅有限，本篇的重点在于二叉树的常见算法以及实现。常见的二叉树实现代码之前写过相关的文章，是关于如何创建及遍历二叉树的，这里不再赘述。同时我们注意到，在二叉树深度比较大的时候，我们光是比较左右是不够的。本篇为复习过程中遇到过的总结，同时也给准备面试的同学一份参考。另外，由于篇幅有限，本篇的重点在于二叉树的常见算法以及实现。常见的二叉树实现代码之前写过相关的文章，是关于如...

YPHP 2019-08-23 12:48 评论0 收藏0
【刷算法】对称的二叉树

摘要：题目描述请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。分析一般关于二叉树的题目，第一直觉是往递归上面靠，当然了，本题适不适合还暂时不知道。题目描述请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。分析一般关于二叉树的题目，第一直觉是往递归上面靠，当然了，本...

Forest10 2019-08-22 18:15 评论0 收藏0