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

题目：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/

代码：

class Solution {

    public Node connect(Node root) {
        if (root != null) {
            if (root.left != null) {
                //左子节点的next
                root.left.next = root.right;
                //递归左子节点
                this.connect(root.left);
            }
            if (root.right != null) {
                //右子节点的next
                if (root.next != null) {
                    root.right.next = root.next.left;
                }
                //递归右子节点
                this.connect(root.right);
            }
        }
        return root;
    }

}

题目要求只能使用常量级额外空间。也就是说不能使用变量，那么我们就考虑是用递归来实现。将题目简化，其实就是要给每个节点的next属性赋值，值为同一层级往右的下一个节点。因为我们使用的是递归的方法，所以对于入参root有如下：

1、root为根节点，所以root没有兄弟节点，则root.next=null，又因为对象的属性默认值为null，所以这种情况我们不处理。
2、root为非根节点，所以root有兄弟节点，则root.next可能有值，这个值取决于它的父节点，但是单从入参我们无法获取父节点，所以我们就将这种情况放在进入递归前的父节点那一层处理。
3、由于2的存在，所以我们在递归root的左右节点时，需要先处理root的左右节点的next的值，左右子节点分情况处理。
4、左子节点，root.left.next=root.right，不用多说。
5、右子节点，情况比较复杂，因为它的next取决于父节点的兄弟节点的子节点，虽然比较绕口，但是由于4的操作在前，所以递归的时候，父节点的next值已经做了处理，所以右子节点root.right.next=root.next.left。
6、综上我们通过递归即可对所有的节点的next属性进行处理，需要注意的是要有非空判断，防止出现空指针异常。

如图所示，图中红色箭头是代码中红色部分建立的联系，即亲兄弟。图中绿色箭头是代码中绿色部分建立的联系，即堂兄弟。