leetcode107：二叉树的层次遍历 #46

Activity

1. sisterAn

   added

   LeetCode

   字节

   on May 20, 2020
2. plane-hjh commented on May 21, 2020

   

   plane-hjh

   on May 21, 2020

   Last edited by plane-hjh

   More actions

   广度优先遍历或者深度优先遍历

   /**
    * Definition for a binary tree node.
    * function TreeNode(val) {
    *     this.val = val;
    *     this.left = this.right = null;
    * }
    */
   /**
    * @param {TreeNode} root
    * @return {number[][]}
    */
   /**
    * 广度优先遍历或者深度优先遍历
    */
   const levelOrderBottom = root => {
     if (!root) return []
     let res = [], queue = [root]
     while (queue.length) {
       let arr = [], temp = []
       while (queue.length) {
         let curr = queue.shift()
         arr.push(curr.val)
         if (curr.left) temp.push(curr.left)
         if (curr.right) temp.push(curr.right)
       }
       queue = temp
       res.push(arr)
     }
     return res.reverse()
   }
3. fanefanes commented on May 21, 2020

   

   fanefanes

   on May 21, 2020

   More actions

   /**
    * Definition for a binary tree node.
    * function TreeNode(val) {
    *     this.val = val;
    *     this.left = this.right = null;
    * }
    */
   /**
    * @param {TreeNode} root
    * @return {number[][]}
    */
   var levelOrderBottom = function(root) {
       const result = []
       dep(root, 0)
       function dep(root,num){
           if(!root) return
           result[num] = result[num]||[]
           result[num].push(root.val)
           dep(root.left, num+1)
           dep(root.right, num+1)
       }
       return result.reverse()
       
   };

   👎React with 👎1Reacted by wei
4. luweiCN commented on May 21, 2020

   

   luweiCN

   on May 21, 2020

   More actions

   使用一个嵌套队列，外层队列保存每层的数据，内层的队列保存当前层所有的节点

   var levelOrderBottom = function (root) {
     if (root === null) return [];
     let queue = [[root]]; // 外层队列
     let print = [];
     while (queue.length) {
       let currentLevel = queue.shift(); // 当前遍历的层，也是一个队列保存的是当前层所有的节点
       let currentLevelVal = [];
       let nextLevel = []; // 准备保存下一层所有的节点
       while (currentLevel.length) {
         let currentNode = currentLevel.shift(); // 遍历当前
         currentLevelVal.push(currentNode.val);
         
         // 根据当前层节点是否有子节点构造下一层的队列
         if (currentNode.left !== null) {
           nextLevel.push(currentNode.left);
         }
         if (currentNode.right !== null) {
           nextLevel.push(currentNode.right);
         }
       }
       
       // 如果下一层队列还有节点，加到外层队列
       if (nextLevel.length) {
         queue.push(nextLevel);
       }
       if (currentLevel.length === 0) {
         print.unshift(currentLevelVal);
       }
     }
   
     return print;
   };

   • 复杂度分析
     时间复杂度：每个节点都会被遍历一次，因此时间复杂度是O(n)
     空间复杂度：需要存储整棵树的值，因此空间复杂度是O(n)
5. zhdxmw commented on May 21, 2020

   

   zhdxmw

   on May 21, 2020

   More actions

   var levelOrderBottom = function(root) {
       let arr = []
       if (!root) return []
       let quene = [root]
       while (quene.length) {
           const queneLength = quene.length
           arr.unshift([])
           for (let i = 0; i < queneLength; i++) {
               const node = quene.shift()
               arr[0].push(node.val)
               node.left && quene.push(node.left)
               node.right && quene.push(node.right)
           }
       }
       return arr
   };
   
6. sisterAn commented on May 21, 2020

   

   sisterAn

   on May 21, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   解法一：BFS（广度优先遍历）

   BFS 是按层层推进的方式，遍历每一层的节点。题目要求的是返回每一层的节点值，所以这题用 BFS 来做非常合适。
   BFS 需要用队列作为辅助结构，我们先将根节点放到队列中，然后不断遍历队列。

   const levelOrderBottom = function(root) {
       if(!root) return []
       let res = [], 
           queue = [root]
       while(queue.length) {
           let curr = [],
               temp = []
           while(queue.length) {
               let node = queue.shift()
               curr.push(node.val)
               if(node.left) temp.push(node.left)
               if(node.right) temp.push(node.right)
           }
           res.push(curr)
           queue = temp
       }
       return res.reverse()
   };

   复杂度分析

   • 时间复杂度：O(n)
   • 空间复杂度：O(n)

   解法二：DFS（深度优先遍历）

   DFS 是沿着树的深度遍历树的节点，尽可能深地搜索树的分支

   DFS 做本题的主要问题是： DFS 不是按照层次遍历的。为了让递归的过程中同一层的节点放到同一个列表中，在递归时要记录每个节点的深度 depth 。递归到新节点要把该节点放入 depth 对应列表的末尾。

   当遍历到一个新的深度 depth ，而最终结果 res 中还没有创建 depth 对应的列表时，应该在 res 中新建一个列表用来保存该 depth 的所有节点。

   const levelOrderBottom = function(root) {
       const res = []
       var dep = function (node, depth){
           if(!node) return
           res[depth] = res[depth]||[]
           res[depth].push(node.val)
           dep(node.left, depth + 1)
           dep(node.right, depth + 1)
       }
       dep(root, 0)
       return res.reverse()   
   };

   复杂度分析：

   • 时间复杂度：O(n)
   • 空间复杂度：O(h)，h为树的高度

   leetcode

   👍React with 👍4Reacted by 程序员依扬, funny-enough, kazusa and Rabbitzzc
7. AnranS commented on Nov 19, 2020

   

   AnranS

   on Nov 19, 2020

   More actions

   var levelOrderBottom = function(root) {
       if(!root) return [];
       let res = [];
       let queue = [root];
   
       while(queue.length) {
           let len = queue.length;
           res.unshift([]);
           for(let i = 0; i < len; i++) {
               let node = queue.shift();
               res[0].push(node.val);
               if(node.left) queue.push(node.left);
               if(node.right) queue.push(node.right);
           }
       }
       return res;
   };
8. Rabbitzzc commented on Mar 28, 2021

   

   Rabbitzzc

   on Mar 28, 2021

   More actions

   DFS 带着递归

   var levelOrder = function (root) {
       // 伴随着队列
       const res = [];
       const traversal = (node, depth) => {
           if (node === null) return
   
           // 如果数组不存在
           if (!res[depth]) {
               res[depth] = []
           }
   
           res[depth].push(node.val)
   
           if (node.left) traversal(node.left, depth + 1)
           if (node.right) traversal(node.right, depth + 1)
       }
       traversal(root, 0)
       return res
   };

   BFS 带着栈

   const levelOrderBottom = (root) => {
       if(!root) return []
   
       let res = [], queue = [root]
   
       while (queue.length) {
           let current = [] // 存储当前队列信息
           let temp = [] // 进入的数据，暂存区
           while (queue.length) {
               const node = queue.shift()
               current.push(node.val)
               if(node.left) temp.push(node.left)
               if(node.right) temp.push(node.right)
           }
           res.push(current)
           queue = temp
       }
   }