116.populating-next-right-pointers-in-each-node.md

116. Populating Next Right Pointers in Each Node

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
      1
    /   \
   2     3
  / \   / \
 4   5 6   7

Output: 
      1 -> null
    /   \
   2 --> 3 -> null
  / \   / \
 4-> 5>6-> 7 -> null

Edge / Corner Cases

• Empty or single node tree

BFS

fun connect(root: Node?): Node? {
    if (root == null) return null
    val queue = ArrayDeque<Node>()
    queue.addLast(root)
    while (queue.isNotEmpty()) {
        val size = queue.size
        for (i in 0 until size) {
            val node = queue.removeFirst()
            node.next = if (i == size - 1) null else queue.first()
            if (node.left != null) queue.addLast(node.left)
            if (node.right != null) queue.addLast(node.right)
        }
    }
    return root
}

• Time Complexity: O(n).
• Space Complexity: O(n).

Recursive

We can start connecting two nodes, and for each two nodes, we can connect their children nodes.

传统的 traverse 函数是遍历二叉树的所有节点，但现在我们想遍历的其实是两个相邻节点之间的「空隙」。这样我们就可以通过这两个节点的 next 指针将它们连接起来。

Nice explanation & Source: https://labuladong.online/algo/data-structure/binary-tree-part1/#%E7%AC%AC%E4%BA%8C%E9%A2%98%E3%80%81%E5%A1%AB%E5%85%85%E8%8A%82%E7%82%B9%E7%9A%84%E5%8F%B3%E4%BE%A7%E6%8C%87%E9%92%88

/**
 *        1
 *     /     \
 *    2       3
 *   / \     / \
 *  4   5   6   7
 */
fun connect(root: Node?): Node? { // connect(1)
    if (root == null) return null
    dfs(root.left, root.right) // dfs(2, 3)
    return root
}

fun dfs(left: Node?, right: Node?) { // dfs(2, 3)
    if (left == null || right == null) return
    left.next = right
    dfs(left.left, left.right)      // 4 -> 5
    dfs(left.right, right.left)     // 5 -> 6
    dfs(right.left, right.right)    // 6 -> 7
}

Space Optimal

TODO: O(1) space complexity.

Take a look at another solution (using the next pointer just built): https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/solution/tian-chong-mei-ge-jie-dian-de-xia-yi-ge-you-ce-2-4/