LeetCode 116. 填充每个节点的下一个右侧节点指针

1、题目

image.png

2、分析

用层序遍历的方法，在遍历都某个结点的时候，再次获取队列中的下一个元素，来填充本结点的next。在遍历完在这一层的时候，将最后一个结点的next置为null

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) return null;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++){
                Node node = queue.poll();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
                node.next = queue.peek();;
                if (i == size - 1) node.next = null;  //判断是否这一层的最后一个结点
            }
        }
        return root;
    }
}

递归：一棵二叉树，都是由以下的两棵小树组成的，用递归，把这两棵小树所有相邻的结点都连接起来就行了

image.png

/*
// 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) return null;
        connectTwoNode(root.left, root.right);
        return root;
    }

    void connectTwoNode(Node node1, Node node2){
        if (node1 == null || node2 == null){
            return;
        }
        node1.next = node2;
        connectTwoNode(node1.left, node1.right);
        connectTwoNode(node2.left, node2.right);
        connectTwoNode(node1.right, node2.left);
    }
}