JavaScript如何實現二叉樹層序遍歷

今天小編給大家分享一下JavaScript如何實現二叉樹層序遍歷的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

題目描述

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

示例

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

返回其層序遍歷結果：

遞歸實現

代碼

  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，如果為空我們直接返回空數組即可，如果不為空繼續我們的代碼運行

• 第二步聲明了兩個變量result用來承接最后的數組，并作為最后的結果返回。deep用來表示當前節點的層級，方便我們向result對應數組中添加元素。

• 然后就到了我們的遞歸方法recursion，recursion的參數是當前節點。在recursion中現實節點深度加一，我們要注意這個深度的流程是，對于二叉樹的結構，向下遞歸一層deep加一，向上return一層deep減一。

• 判斷result對應該層的數組元素是否存在，如果不存在直接等于[root]，如果存在則選擇push方式添加當前root。

• 添加完當前節點就需要判斷，當前節點的左節點是否存在，如果存在將當前節點的左節點作為參數遞歸調用當前recursion函數，如果不存在則跳過

• 當前節點的右節點是否存在，如果存在將當前節點的右節點作為參數遞歸調用當前recursion函數，如果不存在則跳過

• 當左節點右節點都不存在則深度減一并向上返回，或者節點的左節點右節點都已經遍歷完畢也是同樣深度減一并向上返回。

• 當全部執行完畢，返回result。

因為我們使用deep變量標識了當前節點的深度，所以在添加元素時可以添加在對應的位置上。算是得到了要求的數組，但是嚴格意義上來說，并不算是層級遍歷。畢竟層級遍歷必須要是使用隊列來解決。

圖示

隊列實現

代碼

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用來承接最后結果，queue承接當前層的全部節點，作為隊列去使用，res去承接當前層queue中取出的節點的val值，items用來承接下一層的全部節點

• 判斷root是都為空，和上面一樣就不詳細解析

• 進入循環，只有當當前層的節點遍歷完畢并且沒有下一層節點的情況下才會跳出循環

• 當前層節點沒有全部取出(queue的長度不為0)，則取出queue中的第一個節點，節點不為null的話將當前節點的val值push如res，并獲取其左右節點push入items

• 當queue全部取出，說明當前層的節點已經全部遍歷完畢，每個節點的val在res數組中，每個節點的左右節點在items中。我們將items賦值給queue來遍歷下一層的全部節點，將res整個數組push入result結果集中，并重置items與res。

• 當前層遍歷完畢并且當前層全部節點都沒有子節點，說明全部節點遍歷完畢，跳出循環

• 返回結果集

以上就是“JavaScript如何實現二叉樹層序遍歷”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。