Share a LeetCode topic each day

5 minutes a day, make progress together!

LeetCode sequence traversal, address: leetcode-cn.com/problems/bi…

The tree node class

class TreeNode(object) :
    def __init__(self, val, left=None, right=None) :
        self.val = val
        self.left = left
        self.right = right
Copy the code

Level traversal

Again, the idea is to place each layer’s traversal nodes as a separate list in the final result list

Before normal level traversal of ideas we can see here: mp.weixin.qq.com/s/4skiCYIhc…

Solution idea (using queue) :

1. Initialize a queue, enqueue the head node, and initialize a result set res;

2. Initialize a temporary queue level_queue and a list level_res, loop through the elements in queue and check whether they are children. If there are children, add the children to level_queue and add the current node to the list level_res

3. Assign level_queue to queue and insert level_res into result set res. Complete the calculation of one layer. Then do point 2

4. Print the result set res

Implemented code

def levelOrderBottom(self, root) :
    res = []
    queue = collections.deque()
    queue.appendleft(root)
    while(queue):
        level_queue = []   # Record the node value of the layer
        level_res = []     Record the node value of the current layer
        for node in queue:
            if node.left:
                level_queue.append(node.left)
            if node.right:
                level_queue.append(node.right)
            level_res.append(node.val)
        Queue queue queue queue queue queue queue queue queue queue
        queue = level_queue
        res.insert(0, level_res)
    return list(res)
Copy the code

I think it’s neat, but the four initialization definitions need to be familiar

The complete code

# -*- coding:utf-8 -*-
# !/usr/bin/env python

import collections

# tree node class
class TreeNode(object) :
    def __init__(self, val, left=None, right=None) :
        self.val = val
        self.left = left
        self.right = right

class Solution(object) :
    def levelOrderBottom(self, root) :
        res = []
        queue = collections.deque()
        queue.appendleft(root)
        while(queue):
            level_queue = []   # Record the node value of the layer
            level_res = []     Record the node value of the current layer
            for node in queue:
                if node.left:
                    level_queue.append(node.left)
                if node.right:
                    level_queue.append(node.right)
                level_res.append(node.val)
            Queue queue queue queue queue queue queue queue queue queue
            queue = level_queue
            res.insert(0, level_res)
        return list(res)


if __name__ == "__main__":
    Create a new node
    root = TreeNode('A')
    node_B = TreeNode('B')
    node_C = TreeNode('C')
    node_D = TreeNode('D')
    node_E = TreeNode('E')
    node_F = TreeNode('F')
    node_G = TreeNode('G')
    node_H = TreeNode('H')
    node_I = TreeNode('I')
    # build a binary tree
    # A
    # / \
    # B C
    # / \ / \
    # D E F G
    # / \
    # H I
    root.left, root.right = node_B, node_C
    node_B.left, node_B.right = node_D, node_E
    node_C.left, node_C.right = node_F, node_G
    node_D.left, node_D.right = node_H, node_I

    s = Solution()
    print(s.levelOrderBottom(root))
Copy the code