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

题目描述

题解

BFS

这道题跟上一道的区别在于不是完美二叉树, 更具有普遍性.

如果不是完美二叉树那么每个节点的next节点就没有强规律性, 比较好的方法是通过BFS做

public Node connect(Node root) {
    if (root==null){
        return null;
    }
    LinkedList<Node> queue = new LinkedList<>();
    queue.addLast(root);
    while (!queue.isEmpty()) {
        int length = queue.size();

        for (int i = 0; i < length; i++) {
            Node temp = queue.poll();

            if (temp.left != null) {
                queue.add(temp.left);
            }
            if (temp.right != null) {
                queue.add(temp.right);
            }


            if (i == length - 1) {
                temp.next = null;
            } else {
                temp.next = queue.element();
            }

        }
    }

    return root;
}