对称二叉树
1、题目
图1
2、题解
递归
终止条件:left和right不等或者left和right都为空
递归:比较\(left.left和right.right\)以及\(left.right和right.left\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
|
class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: if not root: return True
def dfs(left,right): if not(left or right): return True if not (left and right): return False if left.val != right.val: return False
return dfs(left.left,right.right) and dfs(left.right,right.left) return dfs(root.left,root.right)
|
迭代
实现思路与递归一样:将比较的两个节点放入队列中,比较完毕后弹出队列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
|
class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: if not root or not (root.left or root.right): return True
que = [root.left, root.right]
while que: left = que.pop(0) right = que.pop(0)
if not (left or right): continue if not (left and right): return False if left.val != right.val: return False que.append(left.left) que.append(right.right)
que.append(left.right) que.append(right.left) return True
|