LeetCode No.116 Populating Next Right Pointers in Each Node

November Challenge

Problem

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Solution

It is a perfect binary tree and the way it runs look really similar to BFS(Breadth-First Search). The perfect tree gives us the benefits that we can count the number for each level by pow(2, level).

Therefore, the code should be simple.

Every time a root is visited, we append it’s springs to the list, and level_count +1. If the level_count variable meets the number of Node, we know it is the last of it’s level, therefore, it’s next will be pointed to None.

The speed should be slow since there is a utilize of pop(), it re-arrange the list as it is called.

As excepted, it is slow, but it passed anyway.

#Plz tell me if you got a better solution !