DDR爱好者之家

Python对称的二叉树多种思路实现方法
站长资源 2024/11/25 佚名
69 1538
DDR爱好者之家 Design By 杰米

对称二叉树的含义非常容易理解，左右子树关于根节点对称，具体来讲，对于一颗对称二叉树的每一颗子树，以穿过根节点的直线为对称轴，左边子树的左节点=右边子树的右节点，左边子树的右节点=左边子树的左节点。所以对称二叉树的定义是针对一棵树，而判断的操作是针对节点，这时可以采取由上到下的顺序，从根节点依次向下判断，只需要重复调用函数，不需要回溯。

题目：对称的二叉树题：

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的

解题思路一：先遍历右子节点再遍历左子节点。注意，我们必须把遍历二叉树时遇到的空指针考虑进来。

class Solution:
  def isSymmetrical(self, pRoot):
    # write code here
    return self.isSymmetricalCore(pRoot,pRoot)
  
  def isSymmetricalCore(self,pRoot1,pRoot2):
    if not pRoot1 and not pRoot2:
      return True
    if not pRoot1 or not pRoot2:
      return False
    if pRoot1.val != pRoot2.val:
      return False
    return self.isSymmetricalCore(pRoot1.left,pRoot2.right) and self.isSymmetricalCore(pRoot1.right,pRoot2.left)

解题思路二：迭代

def isSymmetric(self, root: 'TreeNode') -> 'bool':
  stack = root and [(root.left, root.right)]    
  while stack:
    p1, p2 = stack.pop()
    if not p1 and not p2: continue
    if not p1 or not p2: return False
    if p1.val != p2.val: return False
    stack.append((p1.left, p2.right))
    stack.append((p1.right, p2.left))
  return True
DDR爱好者之家 Design By 杰米
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
DDR爱好者之家 Design By 杰米
ddrfans.com DDR爱好者之家
8,675无损音乐
1,324高清电影
213破解软件
70,141收录资讯

更新日志

友情链接

杰晶网络 DDR爱好者之家 南强小屋 黑松山资源网 白云城资源网
DDR爱好者之家 Design By 杰米