iframe-proxy | Sunbelt Computer Software

100 lines (84 loc) · 2.15 KB

# Time:  O(n)
# Space: O(h)
# Invert a binary tree.
#  / \   / \
#  / \   / \
# Time:  O(n)
# Space: O(w), w is the max number of the nodes of the levels.
import collections
# BFS solution.
class Queue:
    def __init__(self):
        self.data = collections.deque()
    def push(self, x):
        self.data.append(x)
    def peek(self):
        return self.data[0]
    def pop(self):
        return self.data.popleft()
    def size(self):
        return len(self.data)
    def empty(self):
        return len(self.data) == 0
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # @param {TreeNode} root
    # @return {TreeNode}
    def invertTree(self, root):
        if root is not None:
            nodes = Queue()
            nodes.push(root)
            while not nodes.empty():
                node = nodes.pop()
                node.left, node.right = node.right, node.left
                if node.left is not None:
                    nodes.push(node.left)
                if node.right is not None:
                    nodes.push(node.right)
        return root
# Time:  O(n)
# Space: O(h)
# Stack solution.
class Solution2:
    # @param {TreeNode} root
    # @return {TreeNode}
    def invertTree(self, root):
        if root is not None:
            nodes = []
            nodes.append(root)
            while nodes:
                node = nodes.pop()
                node.left, node.right = node.right, node.left
                if node.left is not None:
                    nodes.append(node.left)
                if node.right is not None:
                    nodes.append(node.right)
        return root
# Time:  O(n)
# Space: O(h)
# DFS, Recursive solution.
class Solution3:
    # @param {TreeNode} root
    # @return {TreeNode}
    def invertTree(self, root):
        if root is not None:
            root.left, root.right = self.invertTree(root.right), \
                                    self.invertTree(root.left)
        return root

Sunbelt Computer Software

PL/B Language Development and Support

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Sunbelt Computer Software

PL/B Language Development and Support

Uh oh!

FilesExpand file tree

invert-binary-tree.py

Latest commit

History

invert-binary-tree.py

File metadata and controls