Method 1: Recursion

Symmetry means that the left and right word counts of the entire binary tree are also symmetrical.

Then compare the left node of the left subtree with the right node of the right subtree, and the right node of the left subtree with the left node of the right subtree. If each node is equal in this structure, then the binary treesymmetry.As long as there is one inequality in the middle, it must be asymmetrical.

Use the recursive method to move the pointers of the left and right subtrees synchronously. When the left subtree moves to the left, the right subtree moves to the right, and vice versa.Check whether the values ​​of the two pointers are equal each time, if they are all equal, return True, and return False as long as they are not equal.

class Solution:def isSymmetric(self, root: Optional[TreeNode]) -> bool:return self.compare(root.left, root.right)def compare(self, p: Optional[TreeNode], q:Optional[TreeNode]) -> bool:if p == None and q == None:return Trueif p == None or q == None:return Falseif p.val != q.val:return Falseelse:return self.compare(p.left, q.right) and self.compare(p.right, q.left)

Complexity Analysis

Time complexity:

Space Complexity:

Complete test code

from typing import Optionalclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def isSymmetric(self, root: Optional[TreeNode]) -> bool:return self.compare(root.left, root.right)def compare(self, p: Optional[TreeNode], q:Optional[TreeNode]) -> bool:if p == None and q == None:return Trueif p == None or q == None:return Falseif p.val != q.val:return Falseelse:return self.compare(p.left, q.right) and self.compare(p.right, q.left)class main:a = Solution()node1 = TreeNode(1)node2 = TreeNode(2)node3 = TreeNode(2)node4 = TreeNode(3)node5 = TreeNode(4)node6 = TreeNode(4)node7 = TreeNode(3)node1.left = node2node1.right = node3node2.left = node4node2.right = node5node3.left = node6node3.right = node7b = a.isSymmetric(node1)print(b)if __name__ == '__main__':main()

Method 2: Iteration

First set up a list and enqueue the binary tree root node root twice.Each time two nodes are extracted from the queue for comparison, if it is empty, it will be skipped, and if it is different, False will be returned.Then the nodes of the next layer are added for comparison.When adding a new layer of nodes, pay attention to enqueue the left and right child nodes of the two nodes in reverse order.

This is repeated, as long as there is an inequality in the middle, it returns False, and when the loop traversal is complete, it returns True.

class Solution:def isSymmetric(self, root: Optional[TreeNode]) -> bool:queue = [root, root]while queue:p, q = queue.pop(), queue.pop()if not p and not q:continueif not p or not q:return Falseif p.val != q.val:return Falsequeue.append(p.left)queue.append(q.right)queue.append(p.right)queue.append(q.left)return True

Complexity Analysis

Time complexity:

Space Complexity: