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

更新時間：2023年03月31日 15:40:40 作者：庸人°

這篇文章主要為大家簡單介紹一下JS中如何實現(xiàn)二叉樹層序遍歷，感興趣的小伙伴可以詳細參考閱讀

題目描述

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

示例

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

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

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

因為我們使用deep變量標識了當前節(jié)點的深度，所以在添加元素時可以添加在對應(yīng)的位置上。算是得到了要求的數(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承接當前層的全部節(jié)點，作為隊列去使用，res去承接當前層queue中取出的節(jié)點的val值，items用來承接下一層的全部節(jié)點
判斷root是都為空，和上面一樣就不詳細解析
進入循環(huán)，只有當當前層的節(jié)點遍歷完畢并且沒有下一層節(jié)點的情況下才會跳出循環(huán)
當前層節(jié)點沒有全部取出(queue的長度不為0)，則取出queue中的第一個節(jié)點，節(jié)點不為null的話將當前節(jié)點的val值push如res，并獲取其左右節(jié)點push入items
當queue全部取出，說明當前層的節(jié)點已經(jīng)全部遍歷完畢，每個節(jié)點的val在res數(shù)組中，每個節(jié)點的左右節(jié)點在items中。我們將items賦值給queue來遍歷下一層的全部節(jié)點，將res整個數(shù)組push入result結(jié)果集中，并重置items與res。
當前層遍歷完畢并且當前層全部節(jié)點都沒有子節(jié)點，說明全部節(jié)點遍歷完畢，跳出循環(huán)
返回結(jié)果集