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[0]
            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