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

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

代码：

class Solution {

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

    /**
     * 获取node节点的子辈中，仅次于left节点的节点
     *
     * @param node
     * @return
     */
    private Node leftChildNode(Node node, Node left) {
        if (node != null) {
            //按照优先级，左，右，next的左右顺序返回，直到都为null
            if (node.left != null && node.left != left) {
                //因为node节点一定是left节点的父节点或者父节点的兄弟
                //所以是否可以返回node节点的left节点判断依据是是不是等于left
                return node.left;
            } else if (node.right != null) {
                return node.right;
            } else {
                return this.leftChildNode(node.next, left);
            }
        }
        return null;
    }

}

本题是116. 填充每个节点的下一个右侧节点指针的进阶，区别是本题中的树不是完美的二叉树，也就是二叉树的左右子节点可能为null，我们需要针对这种情况进行特殊处理，其他思路跟116的思路一样。

因为节点可能会有空值，所以我们抽了一个leftChildNode方法用于获取node节点的子辈中，小于left节点的节点，具体思路就是使用node节点的next值一直往下找，直到找到有一个有子节点，且按照左右节点的顺序返回最大的节点，也是递归。

另一个需要注意的是，我们在connect方法中的递归执行顺序也需要相应的做调整，因为在leftChildNode方法中，需要使用到next的值，所以我们要保证在connect方法中，next的值是最先建立起来的，之后再递归左右子树。否则会因为next的值还未建立导致出现错误的结果。