?
? ? ? ? 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);
? ? }