Metaapp development interview questions

1. Binary tree , The first line is from left to right   The second line is from right to left

leetcode: Power button

1. Special case handling ： When the root node of the tree is empty , The empty list is returned directly [] ;
2. initialization ： Print results empty list res , Double ended queue with root node deque ;
3.BFS loop ： When deque Jump out when empty ;
         New list tmp , Used to temporarily store the print results of the current layer ;
         Current layer print cycle ： The number of cycles is the number of nodes in the current layer （ namely deque length ）;
         Out of the team ： The first element out of the team , Write it down as node;
         Print ： If it is an odd number of layers , take node.val Added to the tmp The tail ; otherwise , Added to the tmp Head ;
         Add child nodes ： if node Left of （ Right ） The child node is not empty , Join in deque ;
         Results the current layer tmp Turn into list And add res ;
         Return value ： Return to the list of print results res that will do ;

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        res, deque = [], collections.deque([root])
        while deque:
            tmp = collections.deque()
            for _ in range(len(deque)):
                node = deque.popleft()
                if len(res) % 2: tmp.appendleft(node.val) #  Even layers  ->  Queue header 
                else: tmp.append(node.val) #  Odd number layer  ->  Queue tail 
                if node.left: deque.append(node.left)
                if node.right: deque.append(node.right)
            res.append(list(tmp))
        return res

2. List flip ：

LeetCode： Power button

Double pointer ： Consider traversing the linked list , And modify when accessing each node  next  Reference point

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre, cur = None, head
        while cur:
            tmp = cur.next  # Staging the next node 
            cur.next = pre  #  change cur Of next Point to 
            pre = cur # pre  Point to cur The location of 
            cur = tmp # cur Point to next node 
        return pre