剑指offer刷题笔记58（python）

题目描述

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

思路1

利用递归

代码1

# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def symmetrical(self,left,right): if left == None and right ==None: return True if left and right: # 注意，在Python中相等要用==，=是赋值的意思 return left.val == right.val and self.symmetrical(left.right,right.left) and self.symmetrical(left.left,right.right) else: return False def isSymmetrical(self, pRoot): # write code here if pRoot == None: return True return self.symmetrical(pRoot.left,pRoot.right)

思路2

非递归，只需要维护一个栈即可，每次只比较一对节点。出栈的时候，相互比较的两个节点一块出栈来进行比较，有以下几种情况：

出栈的两个节点，都为空，继续（空节点也可以入栈，值为None）出栈的两个节点一个为空，一个不为空，返回False出栈的两个节点的值不相等，返回False 比较完这两个节点之后，需要将这两个节点的子节点入栈（即使子节点为空，也要入栈，值为None）。由于是检查对称二叉树，因此左右子节点要分别对应入栈，即p.left和q.right一块，p.right和q.left一块。 然后再进行下一次循环，若栈为空时，仍没有返回False，那么这颗二叉树就是对称，返回True

代码2

# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def isSymmetrical(self, pRoot): # write code here if pRoot == None: return True if pRoot.left == None and pRoot.right == None: return True p = pRoot.left q = pRoot.right stack = [p,q] # 空节点也可以入栈，为None，但是空节点就没有左右子节点了。 while stack: p = stack.pop() q = stack.pop() if p == None and q == None: # 都为空继续 continue elif p == None or q == None: # 有一个不为空，另一个为空，返回False return False elif p.val != q.val: # 值不相等，不对称，返回False return False else: # 当两个节点，都不为空，且值相等时，将两个节点对应的四个子节点 # 按照顺序依次入栈， 使之两两贴在一块，出栈的时候一块出栈，进行比较。 stack.append(p.left) stack.append(q.right) stack.append(p.right) stack.append(q.left) return True