day25-2022.11.21
题目信息来源
作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm
来源：力扣（LeetCode）
剑指 Offer 28. 对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
输入：root = [1,2,2,3,4,4,3]
输出：true
输入：root = [1,2,2,null,3,null,3]
输出：false
限制：
0 <= 节点个数 <= 1000
题解：辅助栈法
遍历树的方式用的是递归，不过这里每次 pop 的时候和 append 的时候有一点设计。每次 pop 出的是一组需要镜像的节点，即前两个节点。然后判断是否镜像
如果都为空，则是镜像，继续 continue只有一方为空，则不是镜像，return False都不为空，比较值：
相同，则是镜像，继续 continue不同，则不是镜像，return False
continue 的情况下，需要 append 的顺序需要注意：并不是父节点下的两个子节点相同就是对的。headnode.left 应该和 tailnode.right 镜像，tailnode.left 应该和 head.right 镜像。所以 append 的时候也应该是这个顺序。看看能不能尝试递归的办法。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:return True
stack = [root.left, root.right]
while stack:
headnode = stack.pop(0)
tailnode = stack.pop(0)
if headnode==None and tailnode==None:continue
if (not headnode and tailnode) or (headnode and not tailnode):return False
if headnode.val!=tailnode.val:return False
stack.append(headnode.left)
stack.append(tailnode.right)
stack.append(headnode.right)
stack.append(tailnode.left)
return True
题解：递归法
递归法总是要考虑好怎么返回，这个是困扰我很久的问题了。（递归参数，终止条件，返回值，递推工作）
递归参数：headnode 和 tailnode，对应关系在辅助栈方法里已经写了。终止条件和返回值：
如果都为空，return True，因为它已经不能迭代了只有一方为空，则不是镜像，return False都不为空，比较值：
相同，则是镜像，迭代不同，则不是镜像，return False 递归和返回值：需要注意的是，除了初始的 root.right 和 root.left 。其他都应该是两组的比较，两个都 True，才是 True。这个也是我一直写不出来的地方。
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def check(headnode, tailnode):
if not headnode and not tailnode:return True
if not headnode or not tailnode or (headnode.val!=tailnode.val):return False
return check(headnode.left, tailnode.right) and check(headnode.right, tailnode.left)
return not root or check(root.left, root.right)
发表评论