给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

    struct Node { int val;

    Node *left;

    Node *right;

    Node *next;

    }

    填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

    初始状态下，所有 next 指针都被设置为 NULL。

    填充每个节点的下一个右侧节点指针【DFS】【BFS】 - 图1

    方法1：广度优先搜索, 得到每一层所有节点，然后依次从前指向后。

    1. /*
    2. // Definition for a Node.
    3. class Node {
    4. public:
    5.     int val;
    6.     Node* left;
    7.     Node* right;
    8.     Node* next;
    10.     Node() : val(0), left(NULL), right(NULL), next(NULL) {}
    12.     Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
    14.     Node(int _val, Node* _left, Node* _right, Node* _next)
    15.         : val(_val), left(_left), right(_right), next(_next) {}
    16. };
    17. */
    19. class Solution {
    20. public:
    22.     // BFS: 遍历每一层完美二叉树结点放到vector中，然后将前一个结点指向后一个。
    23.     void bfs(Node * node)
    24.     {
    25.         queue<Node *> Q;
    26.         Q.push(node->left);
    27.         Q.push(node->right);
    28.         while(!Q.empty())
    29.         {
    30.             int n = Q.size();
    31.             Node * firstNode = Q.front();
    32.             Q.pop();
    33.             if (firstNode->left) Q.push(firstNode->left);
    34.             if (firstNode->right) Q.push(firstNode->right);
    36.             for(int i=1; i<n; ++i)
    37.             {
    38.                 Node * secondNode = Q.front();
    39.                 Q.pop();
    40.                 firstNode->next = secondNode;
    41.                 firstNode = secondNode;
    43.                 if (secondNode->left) Q.push(secondNode->left);
    44.                 if (secondNode->right) Q.push(secondNode->right);
    45.             }
    46.         }
    47.     }
    49.     Node* connect(Node* root) 
    50.     {
    51.         if (!root || (!root->left && !root->right))
    52.             return root;
    53.         bfs(root);
    54.         return root;
    55.     }
    56. }

    方法2：DFS深度优先搜索

    1. // DFS
    2. void dfs(Node * node)
    3. {
    4.     // 达到叶子节点
    5.     if (!node->left && !node->right)
    6.         return;
    7.     Node * child_left = node->left;
    8.     Node * child_right = node->right;
    9.     // 将以node为根结点的左子树与右子树对应结点都连上。
    10.     while(child_left != nullptr)
    11.     {
    12.         child_left->next = child_right;
    13.         child_left = child_left->right;
    14.         child_right = child_right->left;
    15.     }
    16.     // node->left为根节点的完美二叉树执行相同的操作；
    17.     dfs(node->left);
    18.     // node->right为根节点的完美二叉树执行相同的操作。
    19.     dfs(node->right);
    20. }
    22. Node* connect(Node* root) 
    23. {
    24.     if (!root) return root;
    25.     dfs(root);
    26.     return root;
    27. }

    引申：如果二叉树不是完美二叉树呢？是任意二叉树呢？上述的代码能够还适用？
    欢迎交流，批评指正！