117. 填充每个节点的下一个右侧节点指针 II（没想到，但是其实蛮简单的）
思路：要用到一个函数，作用是找这个根节点root的最右侧子节点的next的指向。打个比方，对于上图里的树，getNextNoNullChild(2)，得到的就是5的next的指向，也就是7，getNextNoNullChild(1)，得到3
之后还可以递归法，直接看代码吧
/*
// 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||(root.left == null && root.right == null))//此时结果为空,记得要返回根节点才对！！！
{
return root;
}
if(root.left!=null&&root.right!=null)//左右子节点都不为空，左节点的next连到右节点，右节点的next用函数求
{
root.left.next=root.right;
root.right.next=getNextNoNullChild(root);
}
if (root.left == null) {//左节点为空，右节点的next用函数求
root.right.next = getNextNoNullChild(root);
}
if (root.right == null) {//。。。。。
root.left.next = getNextNoNullChild(root);
}
// //这里要注意：先递归右子树，否则右子树根节点next关系没建立好，左子树到右子树子节点无法正确挂载
root.right=connect(root.right);
root.left = connect(root.left);
return root;
}
private static Node getNextNoNullChild(Node root)
{
while(root.next!=null)
{
if(root.next.left!=null)
{
return root.next.left;
}
else if(root.next.right!=null)
{
return root.next.right;
}
root = root.next;
}
return null;
}
}