LeetCode 101 Symmetric Tree

LeetCode

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

**Input:** root = [1,2,2,3,4,4,3]
**Output:** true

Example 2:

**Input:** root = [1,2,2,null,3,null,3]
**Output:** false

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• -100 <= Node.val <= 100

Follow up: Could you solve it both recursively and iteratively?

题目大意：

判断二叉树是否对称

解题思路：

Easy题，但难点是转化成比较两棵树是否对称

解题步骤：

N/A

注意事项：

1. 难点是转化成比较两棵树是否对称
2. 还要比较值相等，root.val == root2.val

Python代码：

def isSymmetric(self, root: TreeNode) -> bool:
	return self.is_symmetric(root.left, root.right)

def is_symmetric(self, root, root2):
	if not root and not root2:
		return True
	if not root or not root2:
		return False
	return root.val == root2.val and self.is_symmetric(root.left, root2.right) and self.is_symmetric(root.right, root2.left)

算法分析：

时间复杂度为O(n)，空间复杂度O(1)