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

题意：

解题思路：

思路：
对每个节点：
1. 左子右子都有，则左子next指向右子，右子next指向findNextChild
2. 只有左子，左子指向findNextChild；
3. 只有右子，右子指向findNextChild；
注意：递归时要先递归右子树，否则上级节点next关系没建好，下级无法成功findNextChild

PHP代码实现：

/**
 * Definition for a Node.
 * class Node {
 *     function __construct($val = 0) {
 *         $this->val = $val;
 *         $this->left = null;
 *         $this->right = null;
 *         $this->next = null;
 *     }
 * }
 */
class Solution {
    /**
     * @param Node $root
     * @return Node
     */
    public function connect($root) {
        if ($root == null) return null;
        if ($root->left != null) {
            $root->left->next = ($root->right != null) ? $root->right : $this->findNextChild($root);
        }
        if ($root->right != null) {
            $root->right->next = $this->findNextChild($root);
        }
        $this->connect($root->right);
        $this->connect($root->left);
        return $root;
    }
    function findNextChild($root) {
        if ($root->next == null) return null;
        while ($root->next != null) {
            if ($root->next->left != null) return $root->next->left;
            if ($root->next->right != null) return $root->next->right;
            $root = $root->next;
        }
        return null;
    }
}

GO代码实现：

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */
func connect(root *Node) *Node {
    if root == nil {
        return nil
    }
    if root.Left == nil && root.Right == nil {
        return root
    }
    if root.Left == nil {
        root.Right.Next = next(root.Next)
    } else {
        root.Left.Next = root.Right
    }
    if root.Right == nil {
        root.Left.Next = next(root.Next)
    } else {
        root.Right.Next = next(root.Next)
    }
    // 需要先递归右子树
    connect(root.Right)
    connect(root.Left)
    return root
}
func next(root *Node) *Node {
    if root == nil {
        return nil
    }
    for ;root != nil; root = root.Next {
        if root.Left != nil {
            return root.Left
        }
        if root.Right != nil {
            return root.Right
        }
    }
    return nil
}