leetcode-116.png

var connect = function (root) {
    if (!root) return root
    var traverse = function (node1, node2) {
        if (!node1 && !node2) return
        node1.next = node2
        traverse(node1.left, node1.right)
        traverse(node2.left, node2.right)
        // 处理不同父，但是相邻的节点
        traverse(node1.right, node2.left)
    }
    traverse(root.left, root.right)
    return root
};

BFS

var connect = function (root) {
    if (!root) return root
    let queue = [root]
    while (queue.length) {
        let size = queue.length
        for (let i = 0; i < size; ++i) {
            let node = queue.shift()
            // 最后一个节点指向为空
            if (i < size - 1) node.next = queue[0]
            if (node.left) queue.push(node.left)
            if (node.right) queue.push(node.right)
        }
    }
    return root
};