例如: 下面这棵二叉树是对称的
下面这棵二叉树不对称。
数据范围:节点数满足
,节点上的值满足
要求:空间复杂度
,时间复杂度
备注:
你可以用递归和迭代两种方法解决这个问题
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param pRoot TreeNode类 # @return bool布尔型 # class Solution: def isSymmetrical(self , pRoot: TreeNode) -> bool: if pRoot is None: return True left, right = pRoot.left, pRoot.right lt, rt = [left], [right] while len(lt) > 0 and len(rt) > 0: one = lt.pop() two = rt.pop() if one is None and two is None: continue if one is None&nbs***bsp;two is None: return False if one.val != two.val: return False o_l = one.left one_r = one.right lt.insert(-1, o_l) lt.insert(-1, one_r) t_l = two.left t_r = two.right rt.insert(-1, t_r) rt.insert(-1, t_l) return True
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param pRoot TreeNode类 # @return bool布尔型 # class Solution: def inorder(self, node1, node2): if not node1 and not node2: return True elif not node1&nbs***bsp;not node2: return False elif node1.val != node2.val: return False if self.inorder(node1.left, node2.right): return self.inorder(node1.right,node2.left) return False def isSymmetrical(self , pRoot: TreeNode) -> bool: # write code here if not pRoot: return True return self.inorder(pRoot.left,pRoot.right)
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param pRoot TreeNode类 # @return bool布尔型 # class Solution: def isSymmetrical(self , pRoot: TreeNode) -> bool: if pRoot: return self.levelOrder(pRoot) else: return True def levelOrder(self , root: TreeNode) -> List[List[int]]: # write code here self.val_list=[] h=root # print(h) l=self.get_next_h(h) while l: l=self.get_next_hh(l) if "0" in self.val_list: return False # print(self.val_list) print(self.val_list) if "0" not in self.val_list: return True else: return False def get_next_h(self,x): self.val_list.append("1") return [x.left,x.right] def get_next_hh(self,x): l_r_list=[] l_r_list_val=[] val_one=[] for one in x: if one: val_one.append(str(one.val)) if one.left: l_r_list.append(one.left) l_r_list_val.append(1) else: l_r_list.append(None) l_r_list_val.append(0) if one.right: l_r_list.append(one.right) l_r_list_val.append(1) else: l_r_list.append(None) l_r_list_val.append(0) print(val_one,l_r_list_val) if val_one: b_v=val_one==val_one[::-1] b_b=l_r_list_val==l_r_list_val[::-1] if len(val_one)==1: self.val_list.append("0") elif b_v and b_b: self.val_list.append("1") else: self.val_list.append("0") return l_r_list
class Solution: def recurssion(self, root1, root2): if not root1 and not root2: return True if not root1 or not root2 or root1.val != root2.val: return False return self.recurssion(root1.left, root2.right) and self.recurssion(root1.right, root2.left) def isSymmetrical(self , pRoot: TreeNode) -> bool: return self.recurssion(pRoot, pRoot)
中序遍历方法 class Solution: def isSymmetrical(self , pRoot: TreeNode) -> bool: if not pRoot: return True midOrder_list = [] midOrder_list = self.midOrder(midOrder_list, pRoot) long = len(midOrder_list) if long % 2 == 0: return False else: mid = long // 2 if midOrder_list[0:mid] == midOrder_list[mid + 1:long][::-1]: return True return False def midOrder(self, midOrder_list: list, pRoot: TreeNode) -> list: if not pRoot: return self.midOrder(midOrder_list, pRoot.left) if not pRoot.left and pRoot.right: midOrder_list.append([]) midOrder_list.append(pRoot.val) if not pRoot.right and pRoot.left: midOrder_list.append([]) self.midOrder(midOrder_list, pRoot.right) return midOrder_list
class Solution: def isSymmetrical(self , pRoot: TreeNode) -> bool: # write code here if not pRoot: return True # if not pRoot.left and not pRoot.right: # return True quene =[pRoot] while quene: c = [] for i in range(len(quene)): node = quene.pop(0) if node: c.append(node.val) quene.append(node.left) quene.append(node.right) else: c.append(0) if c != c[::-1]: return False if node != pRoot and len(c) % 2 != 0: return False return True
class Solution: def isSymmetrical(self , pRoot: TreeNode) -> bool: import operator temp1 = [] temp2 = [] def left2right(proot, temp1): if proot is None: temp1.append(1001) return temp1.append(proot.val) left2right(proot.left, temp1) left2right(proot.right, temp1) def right2left(proot, temp2): if proot is None: temp2.append(1001) return temp2.append(proot.val) right2left(proot.right, temp2) right2left(proot.left, temp2) left2right(pRoot, temp1) right2left(pRoot, temp2) # print(temp1, temp2) if operator.eq(temp1, temp2): return True else: return False
class Solution: '''法1:递归但不构造虚拟结点,改成多参数递归即可''' def isSym(self, p_left, p_right): if not p_left and not p_right: return True if not p_left&nbs***bsp;not p_right: return False if p_left.val != p_right.val: return False return self.isSym(p_left.left, p_right.right) and self.isSym(p_left.right, p_right.left) def isSymmetrical(self , pRoot: TreeNode) -> bool: return True if not pRoot else self.isSym(pRoot.left, pRoot.right)方法2:构造对称轴虚拟结点,用原函数递归
class Solution: def isSymmetrical(self , pRoot: TreeNode) -> bool: '''法2:构造对称轴结点递归''' if not pRoot: return True if not pRoot.left and not pRoot.right: return True if not pRoot.left or not pRoot.right: return False if pRoot.left.val != pRoot.right.val: return False virtual_node_1, virtual_node_2 = TreeNode(0), TreeNode(0) virtual_node_1.left, virtual_node_1.right = pRoot.left.left, pRoot.right.right virtual_node_2.left, virtual_node_2.right = pRoot.left.right, pRoot.right.left return self.isSymmetrical(virtual_node_1) and self.isSymmetrical(virtual_node_2)方法3:用队列
class Solution: def isSymmetrical(self , pRoot: TreeNode) -> bool:) '''法1:队列''' if not pRoot: return True if not pRoot.left and not pRoot.right: return True if not pRoot.left&nbs***bsp;not pRoot.right: return False queue_l, queue_r = [pRoot.left], [pRoot.right] while queue_l != [] and queue_r != []: if queue_l[0].val != queue_r[0].val: return False l_pop, r_pop = queue_l.pop(0), queue_r.pop(0) if l_pop.left: if not r_pop.right: return False queue_l.append(l_pop.left) queue_r.append(r_pop.right) if l_pop.right: if not r_pop.left: return False queue_l.append(l_pop.right) queue_r.append(r_pop.left) return queue_l == [] and queue_r == []
class Solution: def isSymmetrical(self , pRoot: TreeNode) -> bool: # write code here if not pRoot: return True return self.helper(pRoot.left, pRoot.right) def helper(self, left, right): if not left and not right: return True if not left and right: return False if left and not right: return False return left.val == right.val and self.helper(left.left, right.right) and self.helper(left.right, right.left)
class Solution: def isSymmetrical(self , pRoot: TreeNode) -> bool: # write code here if not pRoot: return True return self.check(pRoot.left, pRoot.right) def check(self, r1, r2): if (not r1) and (not r2): return True elif r1 and r2: if r1.val != r2.val: return False return self.check(r1.left, r2.right) and self.check(r1.right, r2.left) return False
class Solution: def isSymmetrical(self, pRoot): def recur(left,right): if not left and not right: return True if not left&nbs***bsp;not right: return False if left.val != right.val: return False return recur(left.left,right.right) and recur(left.right,right.left) if not pRoot: return True return recur(pRoot.left, pRoot.right)
## 先翻转左子树再判断左右子树是否相等,空间O(1) class Solution: def isSymmetrical(self , pRoot: TreeNode) -> bool: # write code here if not pRoot&nbs***bsp;(not pRoot.left and not pRoot.right): return True if pRoot.left and pRoot.right: ## Mirror left arr = [pRoot.left] while arr: top = arr[0] arr = arr[1:] tmp = top.left top.left = top.right top.right = tmp if top.left: arr.append(top.left) if top.right: arr.append(top.right) arr = [pRoot.left] arr2 = [pRoot.right] while arr: top = arr[0] top2 = arr2[0] if ( top.val != top2.val&nbs***bsp; (bool(top.left is None) ^ bool(top2.left is None))&nbs***bsp; (bool(top.right is None) ^ bool(top2.right is None))&nbs***bsp; (top.left is not None and top.left.val != top2.left.val)&nbs***bsp; (top.right is not None and top.right.val != top2.right.val) ): return False else: arr = arr[1:] arr2 = arr2[1:] if top.left: arr.append(top.left) arr2.append(top2.left) if top.right: arr.append(top.right) arr2.append(top2.right) return True else: return False
class Solution: def isSym(self,left,right): if left==None and right==None: return True if left==None&nbs***bsp;right==None&nbs***bsp;left.val!=right.val: return False return self.isSym(left.left, right.right) and self.isSym(left.right, right.left) def isSymmetrical(self, pRoot): # write code here if pRoot==None: return True return self.isSym(pRoot.left,pRoot.right)