• 题目：https://www.nowcoder.com/practice/fdbd05d647084fcf9be78444e231998b?tpId=46&tqId=29064&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
  
  
• 题目翻译：

  给定一个二叉树     struct TreeLinkNode {       TreeLinkNode * left;       TreeLinkNode * right;       TreeLinkNode * next;     }}填充每个下一个指针指向其右下角节点。 如果没有下一个右节点，则下一个指针应该设置为NULL。最初，所有下一个指针都设置为NULL。注意：     您只能使用常量额外空间。     你可以假设它是一个完美的二叉树（即所有的叶子在同一层，每个父母有两个孩子）。例如，给定以下完美的二叉树，          1        /        2 3      / \ /      4 5 6 7调用你的函数后，树应该看起来像：          1 - > NULL        /        2 - > 3 - > NULL      / \ /      4-> 5-> 6-> 7 - > NULL

   

• 思路：这道题目的思路就是递归法解决。先是处理简单情况下面的问题，然后再去分别处理左右子树的问题。
• 代码：

  /** * 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 == NULL)            return;        if (root->left != NULL && root->right != NULL)            root->left->next = root->right;                if (root->next != NULL && root->right != NULL)            root->right->next = root->next->left;        connect(root->left);        connect(root->right);            }};

   

• 题目二：升级版本：https://www.nowcoder.com/practice/f18bc13a954f4389900b56e545feca6e?tpId=46&tqId=29063&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
• 题目翻译：

  跟进问题“在每个节点中填充下一个右指针”。如果给定的树可以是任何二叉树？ 您以前的解决方案是否仍然有效？注意：     您只能使用常量额外空间。例如，给定以下二叉树，          1        /        2 3      / \      4 5 7调用你的函数后，树应该看起来像：          1 - > NULL        /        2 - > 3 - > NULL      / \      4-> 5 - > 7 - > NULL

   

• 思路：这道题目看起来和前面的题目好像类似，但是他是针对普通的二叉树，而不是完全二叉树。这一类的问题看前来更像是层次遍历的问题，用层次遍历的思想很容易解决。
  　　对每一个根节点判断他的左右子树是否为空，不为空进入队列.然后特殊处理一个队列尾节点,用来标志某个节点的next为NULL。当当前节点等于队列的尾节点，说明当前节点的next必为NULL。
  
  
  代码：

  /** * 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 == NULL)            return ;        queue<TreeLinkNode *> dq;        TreeLinkNode *tail= root;        TreeLinkNode *temp = NULL;        dq.push(root);        while (!dq.empty()){            temp = dq.front();            dq.pop();            if (temp->left != NULL)                dq.push(temp->left);            if (temp->right != NULL)                dq.push(temp->right);            if (temp == tail){                temp->next = NULL;                tail= dq.back();            }            else                temp->next = dq.front();        }            }};

   

给定一个二叉树

     struct TreeLinkNode {
       TreeLinkNode * left;
       TreeLinkNode * right;
       TreeLinkNode * next;
     }}


填充每个下一个指针指向其右下角节点。 如果没有下一个右节点，则下一个指针应该设置为NULL。

最初，所有下一个指针都设置为NULL。

注意：

     您只能使用常量额外空间。
     你可以假设它是一个完美的二叉树（即所有的叶子在同一层，每个父母有两个孩子）。


例如，
给定以下完美的二叉树，

          1
        / \
       2 3
      / \ / \
     4 5 6 7


调用你的函数后，树应该看起来像：

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

（树）每一层节点的右指针问题（层次遍历）