Python/data_structures/binary_tree/mirror_binary_tree.py at master · twilight-debugger/Python · 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
"""
Given the root of a binary tree, mirror the tree, and return its root.

Leetcode problem reference: https://leetcode.com/problems/mirror-binary-tree/
"""

from __future__ importannotations

fromcollections.abcimportIterator
fromdataclassesimportdataclass


@dataclass
classNode:
"""
 A Node has value variable and pointers to Nodes to its left and right.
 """

value: int
left: Node|None=None
right: Node|None=None

def__iter__(self) ->Iterator[int]:
ifself.left:
yieldfromself.left
yieldself.value
ifself.right:
yieldfromself.right

def__len__(self) ->int:
returnsum(1for_inself)

defmirror(self) ->Node:
"""
 Mirror the binary tree rooted at this node by swapping left and right children.

 >>> tree = Node(0)
 >>> list(tree)
 [0]
 >>> list(tree.mirror())
 [0]
 >>> tree = Node(1, Node(0), Node(3, Node(2), Node(4, None, Node(5))))
 >>> tuple(tree)
 (0, 1, 2, 3, 4, 5)
 >>> tuple(tree.mirror())
 (5, 4, 3, 2, 1, 0)
 """
self.left, self.right=self.right, self.left
ifself.left:
self.left.mirror()
ifself.right:
self.right.mirror()
returnself


defmake_tree_seven() ->Node:
r"""
 Return a binary tree with 7 nodes that looks like this:
 ::

 1
 / \
 2 3
 / \ / \
 4 5 6 7

 >>> tree_seven = make_tree_seven()
 >>> len(tree_seven)
 7
 >>> list(tree_seven)
 [4, 2, 5, 1, 6, 3, 7]
 """
tree=Node(1)
tree.left=Node(2)
tree.right=Node(3)
tree.left.left=Node(4)
tree.left.right=Node(5)
tree.right.left=Node(6)
tree.right.right=Node(7)
returntree


defmake_tree_nine() ->Node:
r"""
 Return a binary tree with 9 nodes that looks like this:
 ::

 1
 / \
 2 3
 / \ \
 4 5 6
 / \ \
 7 8 9

 >>> tree_nine = make_tree_nine()
 >>> len(tree_nine)
 9
 >>> list(tree_nine)
 [7, 4, 8, 2, 5, 9, 1, 3, 6]
 """
tree=Node(1)
tree.left=Node(2)
tree.right=Node(3)
tree.left.left=Node(4)
tree.left.right=Node(5)
tree.right.right=Node(6)
tree.left.left.left=Node(7)
tree.left.left.right=Node(8)
tree.left.right.right=Node(9)
returntree


defmain() ->None:
r"""
 Mirror binary trees with the given root and returns the root

 >>> tree = make_tree_nine()
 >>> tuple(tree)
 (7, 4, 8, 2, 5, 9, 1, 3, 6)
 >>> tuple(tree.mirror())
 (6, 3, 1, 9, 5, 2, 8, 4, 7)

 nine_tree::

 1
 / \
 2 3
 / \ \
 4 5 6
 / \ \
 7 8 9

 The mirrored tree looks like this::

 1
 / \
 3 2
 / / \
 6 5 4
 / / \
 9 8 7
 """
trees= {"zero": Node(0), "seven": make_tree_seven(), "nine": make_tree_nine()}
forname, treeintrees.items():
print(f" The {name} tree: {tuple(tree)}")
# (0,)
# (4, 2, 5, 1, 6, 3, 7)
# (7, 4, 8, 2, 5, 9, 1, 3, 6)
print(f"Mirror of {name} tree: {tuple(tree.mirror())}")
# (0,)
# (7, 3, 6, 1, 5, 2, 4)
# (6, 3, 1, 9, 5, 2, 8, 4, 7)


if__name__=="__main__":
importdoctest

doctest.testmod()
main()