Leetcode--Java--116. 填充每个节点的下一个右侧节点指针

修改BFS + 找规律

1. 修改BFS，不需要用到队列（O（n）），直接利用next特性。
   
2. 当前结点左孩子的next指向右孩子，右孩子的next指向宽搜中当前结点下一个的左孩子。
3. 左孩子的next一定不为空，注意判断右孩子的next是否为空。
4. 利用root不断取左孩子往下层层遍历。

class Solution {
    public Node connect(Node root) {
        if (root == null) return root;
          //先保存根结点，因为后面会改变
          Node originalRoot = root;
          //当下一层不为空
          while (root.left != null) {
              for (Node p = root; p != null; p = p.next) {
                  //当前结点左孩子的next一定Wie右孩子
                  p.left.next = p.right;
                  //右孩子不一定有next，先判断是否为空
                  if (p.next != null) {
                      p.right.next = p.next.left;
                  }
              }
              root = root.left;
          }
          return originalRoot;
    }
}