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 = Noneclass Solution:def isSymmetric(self, root: TreeNode) -> bool:if not root:return Truestack = [root.left, root.right]while stack:headnode = stack.pop(0)tailnode = stack.pop(0)if headnode==None and tailnode==None:continueif (not headnode and tailnode) or (headnode and not tailnode):return Falseif headnode.val!=tailnode.val:return Falsestack.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 Trueif not headnode or not tailnode or (headnode.val!=tailnode.val):return Falsereturn check(headnode.left, tailnode.right) and check(headnode.right, tailnode.left)return not root or check(root.left, root.right)