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

Sequence traversal

Sequence traversal is more important!

Firstly, the sequence itself is a KIND of BFS idea. As the most basic topic, it is often asked in the school admissions.

Secondly, when solving some other types of problems, the idea of BFS can be used as the basic solution of many problems, which will be used many times in the following problems.

General solution idea (assisted by queue) :

1. Initialize a queue and add the head node to the queue.

2. Queue Displays the first node element in the queue and prints it

3. Check whether node has left and right children. If so, join the left and right children in order, then proceed to point 2. Otherwise, proceed directly to Point 2

Implemented code

def level_order_traverse(self, head) :
    if not head:
        return
    queue = [head]
    while len(queue) > 0:
        tmp = queue.pop(0)
        print(tmp.value, end="")
        if tmp.left:
            queue.append(tmp.left)
        if tmp.right:
            queue.append(tmp.right)
Copy the code

And in their case, they want the output to look something like this. That is, output each line as a list

Binary tree: [3,9,20, null, null, 15, 7], 3/20 / \ \ 9 15 7 returns to its sequence traversal results: [[3], [9], [15, 7]]Copy the code

We should make some changes to the output, which needs to be saved separately as each line is iterated through, and then merged into the final array.

The portion that is kept separately is iterated over to update the node of the next level into another array.

Look at the code

class Solution(object) :
    def levelOrder(self, root) :
        res = []
        if not root:
            return res
        queue = [root]
        while queue:
            tmp_queue = []      Record each layer node temporarily
            tmp_res = []        Temporarily record the node value of each row
            for node in queue:
                tmp_res.append(node.val)
                if node.left:
                    tmp_queue.append(node.left)
                if node.right:
                    tmp_queue.append(node.right)
            queue = tmp_queue
            res.append(tmp_res)
        return res
Copy the code

It’s a very small operation

The complete code

Including test cases

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

# 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 levelOrder(self, root) :
        res = []
        if not root:
            return res
        queue = [root]
        while queue:
            tmp_queue = []      Record each layer node temporarily
            tmp_res = []        Temporarily record the node value of each row
            for node in queue:
                tmp_res.append(node.val)
                if node.left:
                    tmp_queue.append(node.left)
                if node.right:
                    tmp_queue.append(node.right)
            queue = tmp_queue
            res.append(tmp_res)
        return 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.levelOrder(root))
Copy the code