Populating next right pointers to each node@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

微博：http://www.weibo.com/cathyhwzn

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *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 toNULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

» Solve this problem

This is the kind of level traversal problem. The first thing pop up in my head is BFS with a queue. Sure we can solve this problem by using a queue. While I found another solution with a better design. When we are working on an question, it's quite important for us to find out the inner logic. And the way we look at it and the logic to solve a question will make a big difference.

The first solution is concise and beautiful without using any container.
The idea of first solution is, use next to keep track of the next spot of "root", and use pre as a pointer to connect nodes in one level. We need to pay attention that all the "next" pointers for all nodes are NULL by default. So we don't need to deal with the last node in each level.