symmetric_tree

Solution

	
	"""
Problem:
https://leetcode.com/problems/symmetric-tree/description/

Solution:
https://www.youtube.com/watch?v=Mao9uzxwvmc

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

def is_symmetric_tree(root):
    """
    :type root: TreeNode
    :rtype: 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)

    if root is None:
        return True
    else:
        return dfs(root.left, root.right)

	

Tests

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

from publicmatt.leet import TreeNode
from publicmatt.leet.problems.symmetric_tree import is_symmetric_tree


def test_empty_tree():
    root = TreeNode.from_list([])
    assert is_symmetric_tree(root)


def test_unbalanced_tree():
    arr = [1, 2, 3, 4, 5]
    root = TreeNode.from_list(arr)
    assert not is_symmetric_tree(root)


def test_mirror():
    arr = [1, 2, 2, 3, 5, 5, 3]
    root = TreeNode.from_list(arr)
    assert is_symmetric_tree(root)


def test_hole():
    arr = [1, 2, 2, 3, 5, 5, None]
    root = TreeNode.from_list(arr)
    assert not is_symmetric_tree(root)


def test_single():
    arr = [1, None, None]
    root = TreeNode.from_list(arr)
    assert is_symmetric_tree(root)