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

116. 填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

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

进阶：

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

运行结果

解题思路
完美二叉树每一层都是左右侧的next指针为空
解决难点是如何实现跨父节点的子节点相连
利用递归的思想，利用两个节点进行遍历，将两个节点的孩子节点相连，可以解决上述问题
java代码

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if(root == null) return root;
        //利用左右两个节点实现连接
        connecthelp(root.left,root.right);
        //最后返回根节点
        return root;
    }
    public void connecthelp(Node a,Node b){
        if(a == null || b == null) return;//完美二叉树有节点为空，则该行为空，直接返回
        a.next=b;//该层两个节点相连
        connecthelp(a.left,a.right);//a节点的左右子树
        connecthelp(a.right,b.left);//a和b之间跨父节点相连
        connecthelp(b.left,b.right);//b节点的左右子树
    }
}