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

/*
// 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) {
        
        // 根节点的next固定为空，不用管，因此直接连接其子节点
        connectSons(root);
        
        return root;
    }

    // 该方法负责将node的左子节点的next指向右子节点，将右子节点的next指向该节点的第一个侄子节点
    // 在调用该方法前，必须先确保node的next已经被设置完成
    private static void connectSons(Node node) {
        
        // 如果当前节点是null或者没有子节点，则无需修改
        if (node == null || (node.left == null && node.right == null)) {
            return;
        }

        // 先获取到当前节点的第一个侄子节点
        Node firstNephew = getFristNephew(node);
        
        // 如果没有右子节点，那么就只有左子节点，此时左子节点的next就是firstNephew
        if (node.right == null) {
            node.left.next = firstNephew;
         
        // 如果有右子节点，则右子节点的next就是firstNephew
        // 而且如果此时还有左子节点，则左子节点的next就是右子节点
        } else {
            node.right.next = firstNephew;
            if (node.left != null) {
                node.left.next = node.right;
            }
        }

        // 递归调用，注意要先连接右边的子树（不然可能会找不到侄子节点）
        // 确保在连接某个节点的子节点时，该节点的next链都已经是正确的值了
        connectSons(node.right);
        connectSons(node.left);
    } 

    // 找到node节点的第一个侄子节点
    private static Node getFristNephew(Node node) {
        Node brother = node.next;
        while (brother != null){
             
            // 如果兄弟节点的左子节点不为空，则兄弟节点的左子节点就是node的第一个侄子节点
            if (brother.left != null) {
                return brother.left;
            }
             
            // 否则，如果兄弟节点的右子节点不为空，则兄弟节点的右子节点就是node的第一个侄子节点
            if (brother.right != null) {
                return brother.right;
            }
             
            // 否则查看下一个兄弟节点
            brother = brother.next;
        }
         
        // 执行到这里，说明没有侄子节点
        return null;
    }
}