There is a binary tree. Please design an algorithm to print the binary tree according to the hierarchy.
Given the root node root of the binary tree, please return the printing results. The results are stored in an array of each layer. All arrays are arranged from top to bottom according to the number of layers, and the elements in the array of each layer are arranged from left to right. Ensure that the number of nodes is less than or equal to 500.
Train of thought 1:
A queue and two pointers last and nlast are used to point to the rightmost node of this layer and the rightmost node of the next layer respectively. Continue to traverse this layer of nodes, with a queue, continue to add the next layer of nodes to the queue. When traversing to the rightmost node of this layer, last is set to nlast
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class TreePrinter: def printTree(self, root): # write code here if not root.left and not root.right: return[[root.val]] res_list =  last = root nlast = None tmp_list =  tmp_list.append(root) line_list =  while tmp_list: node = tmp_list tmp_list.pop(0) line_list.append(node.val) if node.left: n_last = node.left tmp_list.append(node.left) if node.right: n_last = node.right tmp_list.append(node.right) if last == node: last = n_last res_list.append(line_list) line_list =  return res_list
Train of thought 2:
Two queues are used to store all nodes of the current layer and the next layer. Traverse the current layer, then traverse the next layer, and re record all nodes of the next layer.
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class TreePrinter: def printTree(self, root): # write code here res_list =  on_list =  next_list =  tmp_list =  on_list.append(root) while on_list: for node in on_list: tmp_list.append(node.val) if node.left: next_list.append(node.left) if node.right: next_list.append(node.right) res_list.append(tmp_list) tmp_list =  on_list = next_list next_list =  return res_list