Python对称的二叉树多种思路实现方法

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

题⽬：对称的⼆叉树题：

请实现⼀个函数，⽤来判断⼀颗⼆叉树是不是对称的。注意，如果⼀个⼆叉树同此⼆叉树的镜像是同样的，定义其为对称的解题思路⼀：先遍历右⼦节点再遍历左⼦节点。注意，我们必须把遍历⼆叉树时遇到的空指针考虑进来。

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

到此这篇关于Python对称的⼆叉树多种思路实现⽅法的⽂章就介绍到这了,更多相关Python对称的⼆叉树内容请搜索以前的⽂章或继续浏览下⾯的相关⽂章希望⼤家以后多多⽀持！