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

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

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

正文

題目地址

給你二叉樹的根結(jié)點(diǎn) root ，請(qǐng)你將它展開為一個(gè)單鏈表：

展開后的單鏈表應(yīng)該同樣使用 TreeNode ，其中 right 子指針指向鏈表中下一個(gè)結(jié)點(diǎn)，而左子指針始終為 null 。
展開后的單鏈表應(yīng)該與二叉樹先序遍歷順序相同。

示例 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

提示：

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

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

解題思路-基礎(chǔ)

本題要求我們把二叉樹拆成單鏈表，但是其實(shí)仍然是二叉樹，只不過(guò)每個(gè)子樹只有右子樹。
最簡(jiǎn)單的辦法就是前序遍歷二叉樹，將節(jié)點(diǎn)放入數(shù)組，然后遍歷前序遍歷獲取到的節(jié)點(diǎn)數(shù)組，構(gòu)造結(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]
    }
}

解題思路-進(jìn)階

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

想要達(dá)到進(jìn)階的要求，就只能使用常量的額外空間，這里其實(shí)我們可以借用一個(gè) current 變量指向當(dāng)前正在處理的節(jié)點(diǎn)，同樣是前序遍歷，每次把當(dāng)前節(jié)點(diǎn)掛到 current 的右子樹上，同時(shí)把 current 的左子樹置為 null，防止出現(xiàn)循環(huán)引用，然后繼續(xù)處理后續(xù)節(jié)點(diǎn)，這樣當(dāng)前序遍歷完成，就把二叉樹處理成了單鏈表狀態(tài)。

代碼實(shí)現(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-二叉樹展開為鏈表，更多關(guān)于前端算法二叉樹展開為鏈表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: