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

JavaScript實(shí)現(xiàn)二叉樹層序遍歷

 更新時間：2023年03月31日 15:40:40   作者：庸人°  
這篇文章主要為大家簡單介紹一下JS中如何實(shí)現(xiàn)二叉樹層序遍歷，感興趣的小伙伴可以詳細(xì)參考閱讀

題目描述

給你一個二叉樹，請你返回其按 層序遍歷 得到的節(jié)點(diǎn)值。 （即逐層地，從左到右訪問所有節(jié)點(diǎn)）。

示例

二叉樹：[3,9,20,null,null,15,7],

返回其層序遍歷結(jié)果：

遞歸實(shí)現(xiàn)

代碼

  var levelOrder = function(root) {
    if (root === null)
        return []
    let result = [];
    let deep = 0;
    recursion(root);

    function recursion(root) {
        deep++;
        if (result[deep - 1])
            result[deep - 1].push(root)
        else
            result[deep - 1] = [root]
        if (root.left != null)
            recursion(root.left)
        if (root.right !== null)
            recursion(root.right)
        deep--
        return
    }
    return result;

};

let root = {
    value: 3,
    left: {
        value: 9,
        left: null,
        right: null
    },
    right: {
        value: 20,
        left: {
            value: 15,
            left: null,
            right: null
        },
        right: {
            value: 7,
            left: null,
            right: null
        }
    }
}

console.log(levelOrder(root))

思路解析

不得不說遞歸雖然性能有些不太友好，但是是最容易被想到的方案。我們來一步一步解析一個流程，捋一下代碼邏輯。

  • 第一步判斷root是否是null，如果為空我們直接返回空數(shù)組即可，如果不為空繼續(xù)我們的代碼運(yùn)行
  • 第二步聲明了兩個變量result用來承接最后的數(shù)組，并作為最后的結(jié)果返回。deep用來表示當(dāng)前節(jié)點(diǎn)的層級，方便我們向result對應(yīng)數(shù)組中添加元素。
  • 然后就到了我們的遞歸方法recursion，recursion的參數(shù)是當(dāng)前節(jié)點(diǎn)。在recursion中現(xiàn)實(shí)節(jié)點(diǎn)深度加一，我們要注意這個深度的流程是，對于二叉樹的結(jié)構(gòu)，向下遞歸一層deep加一，向上return一層deep減一。
  • 判斷result對應(yīng)該層的數(shù)組元素是否存在，如果不存在直接等于[root]，如果存在則選擇push方式添加當(dāng)前root。
  • 添加完當(dāng)前節(jié)點(diǎn)就需要判斷，當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)是否存在，如果存在將當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)作為參數(shù)遞歸調(diào)用當(dāng)前recursion函數(shù)，如果不存在則跳過
  • 當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)是否存在，如果存在將當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)作為參數(shù)遞歸調(diào)用當(dāng)前recursion函數(shù)，如果不存在則跳過
  • 當(dāng)左節(jié)點(diǎn)右節(jié)點(diǎn)都不存在則深度減一并向上返回，或者節(jié)點(diǎn)的左節(jié)點(diǎn)右節(jié)點(diǎn)都已經(jīng)遍歷完畢也是同樣深度減一并向上返回。
  • 當(dāng)全部執(zhí)行完畢，返回result。

因?yàn)槲覀兪褂?code>deep變量標(biāo)識了當(dāng)前節(jié)點(diǎn)的深度，所以在添加元素時可以添加在對應(yīng)的位置上。算是得到了要求的數(shù)組，但是嚴(yán)格意義上來說，并不算是層級遍歷。畢竟層級遍歷必須要是使用隊(duì)列來解決。

圖示

隊(duì)列實(shí)現(xiàn)

代碼

var levelOrder = function(root) {
    let result = []
    if (!root) return result
    let queue = [root]

    let res = []
    let items = []
    while (queue.length != 0 || items.length != 0) {
        if (!queue.length) {
            queue = items
            result.push(res)
            items = []
            res = []
        }
        let nowRoot = queue.shift()
        if (nowRoot) {
            res.push(nowRoot.val);
            items.push(nowRoot.left)
            items.push(nowRoot.right)
        }
    }
    return result
};

思路解析

  • 同樣result用來承接最后結(jié)果，queue承接當(dāng)前層的全部節(jié)點(diǎn)，作為隊(duì)列去使用，res去承接當(dāng)前層queue中取出的節(jié)點(diǎn)的val值，items用來承接下一層的全部節(jié)點(diǎn)
  • 判斷root是都為空，和上面一樣就不詳細(xì)解析
  • 進(jìn)入循環(huán)，只有當(dāng)當(dāng)前層的節(jié)點(diǎn)遍歷完畢并且沒有下一層節(jié)點(diǎn)的情況下才會跳出循環(huán)
  • 當(dāng)前層節(jié)點(diǎn)沒有全部取出(queue的長度不為0)，則取出queue中的第一個節(jié)點(diǎn)，節(jié)點(diǎn)不為null的話將當(dāng)前節(jié)點(diǎn)的val值push如res，并獲取其左右節(jié)點(diǎn)push入items
  • 當(dāng)queue全部取出，說明當(dāng)前層的節(jié)點(diǎn)已經(jīng)全部遍歷完畢，每個節(jié)點(diǎn)的val在res數(shù)組中，每個節(jié)點(diǎn)的左右節(jié)點(diǎn)在items中。我們將items賦值給queue來遍歷下一層的全部節(jié)點(diǎn)，將res整個數(shù)組push入result結(jié)果集中，并重置items與res。
  • 當(dāng)前層遍歷完畢并且當(dāng)前層全部節(jié)點(diǎn)都沒有子節(jié)點(diǎn)，說明全部節(jié)點(diǎn)遍歷完畢，跳出循環(huán)
  • 返回結(jié)果集

 到此這篇關(guān)于JavaScript實(shí)現(xiàn)二叉樹層序遍歷的文章就介紹到這了,更多相關(guān)JS二叉樹層序遍歷內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

最新評論