EEPW论坛

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

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

题意：把每一层节点链接起来

思路：层次遍历的思想，将一层的元素全部入队，然后将本层每个节点的子节点一次全部入队

1. class Solution  

2. {  

3. public:  

4.     void connect(TreeLinkNode* root)  

5.     {  

6.         if (root==NULL)  

7.         {  

8.             return;  

9.         }  

10.   

11.         TreeLinkNode* tail = root;  

12.         TreeLinkNode* tmp;  

13.         queue<TreeLinkNode*> q;  

14.   

15.         q.push(root);  

16.         while (q.size())  

17.         {  

18.             tmp = q.front();  

19.             q.pop();  

20.   

21.             if (tmp->left!=NULL)  

22.             {  

23.                 q.push(tmp->left);  

24.             }  

25.             if (tmp->right!=NULL)  

26.             {  

27.                 q.push(tmp->right);  

28.             }  

29.               

30.             if(tmp==tail)  

31.             {  

32.                 tmp->next = NULL;  

33.                 tail = q.back();  

34.             }  

35.             else  

36.             {  

37.                 tmp->next = q.front();  

38.             }  

39.   

40.         }  

41.     }  

42. };