Recursively invert the binary tree by swapping the left and right children of every node. At each node, swap its two children, then recursively invert the left and right subtrees. The base case is when the node is None.
Use a queue to perform a breadth-first traversal of the tree. At each node, swap its left and right children, then add both children to the queue. Continue until all nodes have been processed.
""" 0226.1 - Invert Binary Tree - Solution 1 - Recursive DFS """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""Tree Node Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
"""Invert Binary Tree Function"""
if not root:
return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
#####################################################################################
# Functions
#####################################################################################
def treeToList(root):
"""Convert tree to list for easy verification"""
if not root:
return []
result, queue = [], [root]
while queue:
node = queue.pop(0)
if node:
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
result.append(None)
while result and result[-1] is None:
result.pop()
return result
def testcase():
"""Test Function"""
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7, TreeNode(6), TreeNode(9)))
print(treeToList(Solution().invertTree(root))) # [4, 7, 2, 9, 6, 3, 1]
root = TreeNode(2, TreeNode(1), TreeNode(3))
print(treeToList(Solution().invertTree(root))) # [2, 3, 1]
print(treeToList(Solution().invertTree(None))) # []
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0226.2 - Invert Binary Tree - Solution 2 - Iterative BFS """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
from collections import deque
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""Tree Node Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
"""Invert Binary Tree Function"""
if not root:
return None
queue = deque([root])
while queue:
node = queue.popleft()
node.left, node.right = node.right, node.left
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
#####################################################################################
# Functions
#####################################################################################
def treeToList(root):
"""Convert tree to list for easy verification"""
if not root:
return []
result, queue = [], [root]
while queue:
node = queue.pop(0)
if node:
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
result.append(None)
while result and result[-1] is None:
result.pop()
return result
def testcase():
"""Test Function"""
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7, TreeNode(6), TreeNode(9)))
print(treeToList(Solution().invertTree(root))) # [4, 7, 2, 9, 6, 3, 1]
root = TreeNode(2, TreeNode(1), TreeNode(3))
print(treeToList(Solution().invertTree(root))) # [2, 3, 1]
print(treeToList(Solution().invertTree(None))) # []
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()