欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

前端算法題解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í)仍然是二叉樹,只不過每個(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)階

上面的解題思路可以完成解題,但是沒有達(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)文章!

相關(guān)文章

最新評(píng)論