# Binary tree printing

## subject

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

## Code 1:

```# -*- 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.

## Code 2:

```# -*- 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
```

Tags: less

Posted on Tue, 05 May 2020 07:31:49 -0700 by eideticmnemonic