dsa/is_symmetric_tree.py at main · 121watts/dsa · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import copy
# For your reference:
class BinaryTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

bst = BinaryTreeNode(1)
# bst.left = BinaryTreeNode(2)
# bst.left.left = BinaryTreeNode(3)
# bst.left.right = BinaryTreeNode(4)
# bst.right = BinaryTreeNode(2)
# bst.right.left = BinaryTreeNode(4)
# bst.right.right = BinaryTreeNode(3)


def check_if_symmetric(root):
    """
    Args:
     root(BinaryTreeNode_int32)
    Returns:
     bool
    """

    is_symmetric = True

    def invert(node):
        if not node:
            return node

        left = node.left
        right = node.right

        node.left = right
        node.right = left

        invert(node.left)
        invert(node.right)

    invert(root.right)

    def is_same(lsub, rsub):
        nonlocal is_symmetric
        if not lsub and not rsub:
            return

        if (lsub and not rsub) or (rsub and not lsub):
            is_symmetric = False
            return

        if lsub.value != rsub.value:
            is_symmetric = False
            return

        is_same(lsub.left, rsub.left)
        is_same(lsub.right, rsub.right)

    is_same(root.left, root.right)

    return is_symmetric

print(check_if_symmetric(bst))