In time, you will call me master -- Star Wars

Week 1 Invert Binary Tree

Solution 1

• using list as stack

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        invert_node = TreeNode()
        queue = []
        queue.append(root)
        while(queue):
            tmp_queue = queue.pop(0)
            if tmp_queue:
                tmp_queue.left, tmp_queue.right = tmp_queue.right, tmp_queue.left
                queue.append(tmp_queue.left)
                queue.append(tmp_queue.right)
        return root

• stack ( last-in , first-out )
• invert binary tree : tmp_queue.left, tmp_queue.right = tmp_queue.right, tmp_queue.left

Solution 2

• using deque ( list as queue )

from collections import deque 
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        invert_node = TreeNode()
        queue = deque([root])
        while queue:
            item = queue.popleft()
            if item:
                item.left, item.right = item.right, item.left
                queue.append(item.left)
                queue.append(item.right)
        return root

• queue ( first-in, last-out )
• queue pop first item -- > popleft()

important take away

• Deques have O(1) speed for appendleft() and popleft()
• lists have O(n) performance for insert(0, value) and pop(0)