leetcode------Populating Next Right Pointers in Each Node

제목:
Populating Next Right Pointers in Each Node
통과율:
36.1%
난이도:
중간
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 to  NULL .
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
 ， 。 ， 。 。


 

 1 /**

 2  * Definition for binary tree with next pointer.

 3  * public class TreeLinkNode {

 4  *     int val;

 5  *     TreeLinkNode left, right, next;

 6  *     TreeLinkNode(int x) { val = x; }

 7  * }

 8  */

 9 public class Solution {

10     public void connect(TreeLinkNode root) {

11         int count=1,tmp=0;

12         LinkedList<TreeLinkNode> queue=new LinkedList<TreeLinkNode>();

13         TreeLinkNode start=null,sec=null,pre=null;

14         if(root!=null){

15          queue.addLast(root);

16         }

17         while(!queue.isEmpty()){

18             pre=queue.pollFirst();

19                 if(count==1)pre.next=null;

20                 if(pre.left!=null){

21                     queue.addLast(pre.left);

22                     tmp++;

23                 }

24                 if(pre.right!=null){

25                     queue.addLast(pre.right);

26                     tmp++;

27                 }

28 

29             for(int i=1;i<count;i++){

30                 start=queue.pollFirst();

31                 pre.next=start;

32                 pre=start;

33                 if(start.left!=null){

34                     queue.addLast(start.left);

35                     tmp++;

36                 }

37                 if(start.right!=null){

38                     queue.addLast(start.right);

39                     tmp++;

40                 }

41             }

42             count=tmp;

43             tmp=0;

44             if(start!=null)

45             start.next=null;

46         }

47         

48     }

49 }