116&117. Populating Next Right Pointers in Each Node I && II

source: https://leetcode.com/problems/populating-next-right-pointers-in-each-node/ source: https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/submissions/

Question

You are given a (perfect) binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node { int val; Node *left; Node *right; Node *next; }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

初想法

116和117唯一的区别就是是否是完美二叉树，但其实如果用bfs来做的话是没有区别的。

这题的核心关系是相同层级间节点的关系，所以是很典型的有层级的bfs发挥的场景。如果用层级遍历的方式做就非常简单。

var connect = function (root) {
    if (!root) return root;
    const list = [];
    const queue = [root];
    while (queue.length) {
        const num = queue.length;
        const sub = [];
        let i = 0;
        while (i < num) {
            i += 1;
            const node = queue.shift();
            if (!node) continue;
            sub.push(node);
            queue.push(node.left);
            queue.push(node.right);
        }
        list.push(sub);
    }
    list.forEach(sub => sub.forEach((node, index) => {
        node.next = sub[index + 1] || null;
    }));
    return root;
};

总结

其实很多题目间是进阶关系，熟练掌握了层级遍历(102), 本题就非常简单。