筆記 — 二元樹節點指右鄰

2021 台灣玉山塔塔加鹿林山

Populating Next Right Pointers in Each Node II - LeetCode

題目有個第一版本，只差是完全二元樹，由於較簡單，這邊就直接先列第一版的答案，BJ4:

採用 DFS(深度優先)，先做左子樹或右子樹都可以。

而第二版是不完全樹，這時就要考慮較多的事情。

root.right?.next = root.next?.left

由於是不完全樹，表示有可能會跨多個空子樹指右鄰，DFS 無法得知跨子樹的資訊，那麼需要依賴 root.next 來尋找跨樹右鄰，所以 DFS 至少我們會先完成右子樹。

connect(root.right)
connect(root.left)

接著要思考空子樹：

root.next == null
root.next.left == null

該怎麼辦？應該繼續往 root.next.next 找，再不行就一直繼續找，而且是要找到 root.next…..left 或者 root.next…right 為止。

fun getNext(root: Node?): Node? {
    if (root == null) {
        return root
    }
    return root.left ?: root.right ?: getNext(root.next)
}

這樣基本上就解決最大的難點了：

時間複雜度 O(2n)

getNext(): 每層跨度/寬度 k (k < n 節點)，最糟狀況就是每層都耗 1k ，所以嚴苛來說時間複雜度是 O(2n)

這邊附上非遞迴的版本，思考框架是二維陣列：

var i = root
while (i != null) { // 往右移動
  ..
  i = i.next
}

時間複雜度 O(n)

使用一維指標換行，這樣要自己換行:

時間複雜度 O(n)