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
};
