117. Populating Next Right Point

题目

在 116 题的基础上，二叉树变为不完美二叉树，然后进行 Next 节点的填充

解析

还是按照 116 题解思路，并不能解决距离差距在 2 的两个不想干子树的链接问题。这里可以考虑利用已经解决的部分，来解决接下来要解决的部分，即 对于两层节点 lv1 和 lv2，我们可以先链接 lv1 层的节点，然后利用 lv1 层的连通性，来解决 lv2 层的链接问题。
例如当 lv1 层链接后，找到 lv2 层第2个节点，查找这个节点的下一个节点，下一个节点是其父节点的非当前节点的第一个子节点。

所以整个树总体采用层序遍历的方式进行，主循环中以 lv1 层为轴，连接 lv2 层的节点，然后再以 lv2 层为轴，链接 lv3 层，这里存在 1 个问题，即每次更换新的一层时，需要记录上一次层的首节点，否则整个循环无法进行下去。

伪代码

connect(node) node

head = node
for head != nil
  for node != nil
    node.left.next = findnext(node)
    node.right.next = findnext(node)
    node = node.next
  head = head.left

findnext(node) node

for node != nil
  if node.left != nil
    return node.left
  if node.right != nil
    return node.right
  node = node.next
return nil

代码

func connect(root *Node) *Node {
    
    head := root
    for head != nil {
        node := head
        for node != nil {
            if node.Left != nil {
                if node.Right != nil {
                    node.Left.Next = node.Right
                }else {
                    node.Left.Next = findnext(node.Next)
                }
            }
            if node.Right != nil {
                node.Right.Next = findnext(node.Next)
            }
            node = node.Next
        }
        head = findnext(head)
    }
    return root
}

func findnext(node *Node) *Node {
    for node != nil {
        if node.Left != nil {
            return node.Left
        }
        if node.Right != nil {
            return node.Right
        }
        node = node.Next
    }
    return nil
}