前端算法題解leetcode114二叉樹展開為鏈表

Posted on by

正文

題目地址

給你二叉樹的根結點 root ，請你將它展開為一個單鏈表：

  • 展開後的單鏈表應該同樣使用 TreeNode ，其中 right 子指針指向鏈表中下一個結點，而左子指針始終為 null 。
  • 展開後的單鏈表應該與二叉樹 先序遍歷 順序相同。

示例 1：

輸入： root = [1,2,5,3,4,null,6]
輸出： [1,null,2,null,3,null,4,null,5,null,6]

示例 2：

輸入： root = []
輸出： []

示例 3：

輸入： root = [0]
輸出： [0

提示：

  • 樹中結點數在范圍 [0, 2000] 內
  • -100 <= Node.val <= 100

進階： 你可以使用原地算法（O(1) 額外空間）展開這棵樹嗎？

解題思路-基礎

本題要求我們把二叉樹拆成單鏈表，但是其實仍然是二叉樹，隻不過每個子樹隻有右子樹。
最簡單的辦法就是前序遍歷二叉樹，將節點放入數組，然後遍歷前序遍歷獲取到的節點數組，構造結果二叉樹。

代碼實現

function treeToList(root){
    const list = []
    function preorder(node){
        if(node === null){
            return
        }
        list.push(node)
        preorder(node.left)
        preorder(node.right)
    }
    preorder(root)
    return list
}
var flatten = function(root) {
    if(root === null){
        return null
    }
    const list = treeToList(root)
    for(let i = 1;i&lt;list.length;i++){
        list[i-1].left = null
        list[i-1].right = list[i]
    }
}

解題思路-進階

上面的解題思路可以完成解題，但是沒有達到本題進階的要求：使用原地算法（O(1) 額外空間）展開這棵樹。

想要達到進階的要求，就隻能使用常量的額外空間，這裡其實我們可以借用一個 current 變量指向當前正在處理的節點，同樣是前序遍歷，每次把當前節點掛到 current 的右子樹上，同時把 current 的左子樹置為 null，防止出現循環引用，然後繼續處理後續節點，這樣當前序遍歷完成，就把二叉樹處理成瞭單鏈表狀態。

代碼實現

var flatten = function(root) {
    if(root === null){
        return null
    }
    let current = {}
    function preorder(node){
        if(node === null){
            return
        }
        current.left = null
        current.right = node
        current = current.right
        const left = current.left
        const right = node.right
        preorder(left)
        preorder(right)
    }
    preorder(root)
}

至此我們就完成瞭 leetcode-114-二叉樹展開為鏈表，更多關於前端算法二叉樹展開為鏈表的資料請關註WalkonNet其它相關文章！

推薦閱讀：