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

更新時間：2022年09月22日 11:29:05 作者：前端_奔跑的蝸牛

這篇文章主要為大家介紹了前端算法題解leetcode114二叉樹展開為鏈表，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

正文

題目地址

給你二叉樹的根結點 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

提示：

樹中結點數(shù)在范圍 [0, 2000] 內(nèi)
-100 <= Node.val <= 100

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

解題思路-基礎

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

代碼實現(xiàn)

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 變量指向當前正在處理的節(jié)點，同樣是前序遍歷，每次把當前節(jié)點掛到 current 的右子樹上，同時把 current 的左子樹置為 null，防止出現(xiàn)循環(huán)引用，然后繼續(xù)處理后續(xù)節(jié)點，這樣當前序遍歷完成，就把二叉樹處理成了單鏈表狀態(tài)。

代碼實現(xiàn)

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-二叉樹展開為鏈表，更多關于前端算法二叉樹展開為鏈表的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: