101.Symmetric_Tree(Easy).md

101. Symmetric Tree (Easy)

Date and Time: Jul 16, 2024, 15:15 (EST)

Link: https://leetcode.com/problems/symmetric-tree/

Question:

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

KeyPoints:

Similar trick to this kind of problem we are checking left node and right node are the same or not. But we are passing dfs(left.left, right.right) and dfs(left.right, right.left) to see if they are all the same, because the mirror of the binary tree will have the root's left-subtree = the root's right-subtree.

My Solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def dfs(left, right):
            if not left and not right:
                return True
            if not left or not 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)

Time Complexity: $O(n)$
Space Complexity: $O(h)$, h is the height of the tree.