leetcode Populating Next Right Pointers in Each Node II
這題和上一題Populating Next Right Pointers in Each Node的不一樣了，這裡要求的是普通的樹，難度就比較大了。之前是簡單的找到左邊的最後，和右邊的最左鏈接就可以了。現在存在的問題是可能右邊的左右一層不是在最左或者長度不一等等。
1
/ \
2 3
/ \ \
4 5 7
得到：
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
如圖：假設先在要處理2為root的時候，那麼我們要判斷2的右子樹存在與否，如果存在，例如圖中的5，那麼我們就要在2的next的子樹中找5的next，那肯定是3的左子樹優先，但是3沒有左子樹，所以再判斷3的右子樹7，然後將7作為5的next，試想，如果3的右子樹也為空，那是不是就沒有5的next了呢，不，我們還要繼續考慮3的next是否是空，如果3的next不為空，那麼就把3的next類似判斷左右子樹看是否有符合5的next的。如果還是沒有那就next的next一直到找到為止，或者next為空為止。
5的next處理的過程中首先要要求3已經處理好了，所以應該先遞歸右子樹。
5的next處理後，在判斷2的左子樹是否為空，如果為空，那麼返回，如果不為空，那麼就將5給4的next，如果沒有5，那就是把剛才找到的本來要給5的next的給4當做next。
那麼就可以有：
復制代碼
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
if (!root) return ;
TreeLinkNode *p = root -> next;
TreeLinkNode *sonNext = NULL;
while (p)//如果next存在，那麼就有可能有值可以給root子樹的next
{
if (p -> left)
{
sonNext = p -> left;
break;
}
else if (p -> right)
{
sonNext = p -> right;
break;
}
else
p = p -> next;
}
if (root -> right)
{
root -> right -> next = sonNext;
if (root -> left)
root -> left -> next = root -> right;
}
else if (root -> left)
root -> left -> next = sonNext;
connect(root -> right);
connect(root -> left);
}
