Leetcode June challenge ( Invert Binary Tree )

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)