一、填充每个节点的下一个右侧节点指针（116—简单）

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

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

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

116、填充每个节点的下一个右侧节点指针 - 图1

二、分析

只有最右侧的节点的指针才为空，同一层的叶子或者节点，都有下一个右侧节点。我们从根结点开始出发，先找到它的左孩子，将左右孩子建立连接。总的来说，还是要搞清楚二叉树问题的大体要求是要干嘛，然后细分到每个节点要干嘛！

三、题解

  1. class Solution {
  2.     public Node connect(Node root) {
  3.         //1、判空
  4.         if (root == null){
  5.             return null;
  6.         }
  7.         //2、如果左孩子节点不为空，建立连接
  8.         if (root.left != null){
  9.             //左孩子连接右孩子
  10.             root.left.next = root.right;
  11.             //如果当前节点的右侧节点不为空
  12.             if (root.next != null){
  13.                 //连接当前节点的右节点与其右侧节点
  14.                 root.right.next = root.next.left;
  15.             }
  16.         }
  17.         connect(root.left);
  18.         connect(root.right);
  19.         return root;
  20.     }
  21. }