LeetCode Js-102. Binary Tree Level Order Traversal

    LeetCode Js-Binary TreeLeetCode Js-DFS/BFS

    Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

    給與二元樹的根,傳回其節點值的層序遍歷。 (即由左至右,逐級)。
    

    Example 1:

    Input: root = [3,9,20,null,null,15,7]
    Output: [[3],[9,20],[15,7]]
    

    Example 2:

    Input: root = []
    Output: []
    

    Example 3:

    Input: root = [1]
    Output: [1]
    

    solution:
    1. 首先,我們要知道 level order traversal(層序遍歷)所指的方向,接著:
    2. 我們在 Level Order Traversal(root) 的函式中接受 binary tree 的輸入,並透過 bfs 來完成前序遍歷的結果。
    3. 我們先判斷 node 是否為 null,如果是則直接返回。
    4. 在 bfs(node, result) 中開始做 node 的遍歷。
    5. 使用一個 queue 來儲存要訪問的節點。這是 BFS 的基本操作。
    6. 在每一次的循環中,我們只考慮當前 queue 中的節點,也就是當前層級的所有節點。
    7. 對於當前層級的每個節點,我們先將其從 queue 中移除,然後將其子節點(如果有的話)加入到 queue 中。
    8. 訪問完當前層級的所有節點後,我們再繼續下一層級的節點,直到 queue 變空。

    ex.
    層序遍歷步驟:
    1. 訪問當前節點
    2. 遍歷左子樹
    3. 遍歷右子樹
    4. 訪問下一節點
    
    附上示意圖: https://ithelp.ithome.com.tw/articles/10289291
    

    Code 1: BFS

    class TreeNode {
      constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
      }
    }
    
    var levelOrder = function(root) {
        // 1. 檢查 root 是否為空
        if (!root) return [];
    
        // 2. 創建一個陣列來存放結果
        const result = [];
    
        // 3. 把根節點放入 BFS 函數中
        bfs(root, result);
    
        return result;
    };
    
    function bfs(node, result) {
        // 初始化
        const queue = [];  // 創建一個隊列來存放節點
        queue.push(node);
    
        // 當隊列不為空時,繼續執行
        while (queue.length) {
            const len = queue.length;
            const row = [];
            // 對當前階層的每一個節點進行處理
            for (let i = 0; i < len; i++) {
                // 從隊列中取出一個節點
                const cur = queue.shift();
    
                // 如果這個節點有左子節點,則將其放入隊列中
                if (cur.left) queue.push(cur.left);
                // 如果這個節點有右子節點,則將其放入隊列中
                if (cur.right) queue.push(cur.right);
    
                // 將當前節點的值加入到 row 陣列中
                row.push(cur.val);
            }
            // 最後,將 row 陣列加入到 output 陣列中
            result.push(row);
        }
    }
    

    FlowChart:
    Example 1

    TreeNode {
      val: 3,
      left: TreeNode { val: 9, left: null, right: null },
      right: TreeNode {
        val: 20,
        left: TreeNode { val: 15, left: null, right: null },
        right: TreeNode { val: 7, left: null, right: null }
      }
    }
    
    TreeNode {
      val: 3,
      left: TreeNode { val: 9, left: null, right: null },
      right: TreeNode {
        val: 20,
        left: TreeNode { val: 15, left: null, right: null },
        right: TreeNode { val: 7, left: null, right: null }
      }
    }
    [ [ 3 ], [ 9, 20 ], [ 15, 7 ] ]
    

    Example 2

    const rootNode = []
    

    Example 3

    TreeNode { val: 1, left: null, right: null }