题目描述

给定一个二叉树

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

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

进阶：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例：
![pic](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/15/117_sample.png)
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

解题思路

该题与上题不一致的地方在于，上题中是棵完全二叉树。不需要考虑next节点存在时，next的left和right不存在的情况。(导致寻找next节点时，需要多次遍历父节点的next节点)。
这里使用递归的方式connect，另外当right不存在时，或者需要给right找next节点时，实现nextNode循环遍历root->next找到下一个节点。另外，递归时先connect(right)，再connect(left)。

Node* connect(Node* root){
        if(root==nullptr)
              return root;
        if(root->left){
                if(root->right)
                      root->left->next = root->right;
                else{
                      root->left->next = nextNode(root->next);
                }
        }
        if(root->right){
                root->right->next = nextNode(root->next);
        }
        connect(root->right);
        connect(root->left);
        return root;
}