# Mirror of Binary Tree

The question is that we need to invert a binary tree by a given string.

The most traditional way is that simulating each step by step:

```import queue

class TreeNode(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None

def str2tree(index):
if index <= length:
val = node_list[index - 1]
node = TreeNode(val)
node.left = str2tree(index * 2)
node.right = str2tree(index * 2 + 1)
return node
else:
return None

def tree2str(root):
result = list()
q = queue.Queue()
q.put(root)

while not q.empty():
cur = q.get()
if cur:
result += [cur.val]
q.put(cur.left)
q.put(cur.right)
else:
result += ["#"]

# while result[-1] == "#":
#     result.pop()

return result

def invertTree(root):
if not root:
return None

root.left, root.right = invertTree(root.right), invertTree(root.left)

return root

def shortcut(string):
index = 1
result = list()
while string:
result += [string[:index]]
string = string[index:]
index *= 2

return "".join([item[::-1] for item in result])

if __name__ == "__main__":
node_list = "427#369"
length = len(node_list)

root = str2tree(1)
root = invertTree(root)
result = tree2str(root)

print(result)```

However, it’s really stupid for contest if you just simulate it. We actually are able to invert segments of the entire string in O(n) time complexity.

``````def shortcut(string):
index = 1
result = list()
while string:
result += [string[:index]]
string = string[index:]
index *= 2

return "".join([item[::-1] for item in result])``````