【LeetCode-中等题】116. 填充每个节点的下一个右侧节点指针

题目

方法一：直接让每层不是最后一个的节点指向此时队首元素

class Solution {
    public Node connect(Node root) {
        if(root == null) return null;
        Deque<Node> queue = new LinkedList<>();
        Node node = root;
        queue.offer(node);
        List<Node> list = null;
        while(!queue.isEmpty()){
            int size = queue.size();
            list = new ArrayList<>();
            for(int i = 0 ; i < size ; i++){
                node = queue.poll();
                //第二种链接方法  ：  直接让每层不是最后一个的节点指向此时队首元素
                if(i == size - 1) node.next = null;//每层最后一个指向 null
                else node.next = queue.peek();//不是最后一个的节点指向此时队首元素
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
        }
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

方法二：用list记录下每层的节点 然后再做链接

class Solution {
    public Node connect(Node root) {
        if(root == null) return null;
        Deque<Node> queue = new LinkedList<>();
        Node node = root;
        queue.offer(node);
        List<Node> list = null;
        while(!queue.isEmpty()){
            int size = queue.size();
            list = new ArrayList<>();
            for(int i = 0 ; i < size ; i++){
                node = queue.poll();
                list.add(node);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            //第一种方法 ： 用list记录下每层的节点  然后再做链接
            for(int i = 0 ; i < list.size() ; i++){
                if(i == list.size()-1) list.get(i).next = null;
                else list.get(i).next = list.get(i+1);
            }
        }
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25