精选留言(19)

• 
  涂改

  2019-03-02

  dfs:
  class Solution {
      public List<List<Integer>> levelOrder(TreeNode root) {
          if(root == null) return new ArrayList<>();
          List<List<Integer>> list = new ArrayList<>();
          dfs(root, list, 1);
          return list;
      }
      
      public void dfs(TreeNode root, List<List<Integer>> list, int level){
          if(root == null) return;
          if(list.size() < level) list.add(new ArrayList<Integer>());
          list.get(level - 1).add(root.val);
          dfs(root.left, list, level + 1);
          dfs(root.right, list, level + 1);
      }
  }

  展开

  作者回复: 帅！！
  

  

   3
• 
  Alexdown

  2019-06-19

  Golang实现
  /**
   * Definition for a binary tree node.
   * type TreeNode struct {
   * Val int
   * Left *TreeNode
   * Right *TreeNode
   * }
   */
  func levelOrder(root *TreeNode) [][]int {
      // return dfsLevelOrder(root)
      return bfsLevelOrder(root)
  }
  
  func bfsLevelOrder(root *TreeNode) [][]int {
      if root == nil {
          return [][]int{}
      }
      
      queue := make([]*TreeNode, 0)
      queue = append(queue, root)
      levels := make([][]int, 0)
      
      for len(queue) > 0 {
          
          n, level := len(queue), make([]int, 0)
          
          for i := 0; i < n; i++ {
              
              root = queue[0]
              queue = queue[1:]
              
              level = append(level, root.Val)
              
              if root.Left != nil {
                  queue = append(queue, root.Left)
              }
              
              if root.Right != nil {
                  queue = append(queue, root.Right)
              }
          }
          
          levels = append(levels, level)
      }
      
      return levels
  }
  
  func dfsLevelOrder(root *TreeNode) [][]int {
      level := 0
      vals := make([][]int, 0)
      dfs(root, level, &vals)
      return vals
  }
  
  func dfs(root *TreeNode, level int, vals *[][]int) {
      //fmt.Println(root, level, vals)
      if root == nil {
          return
      }
      
      if len(*vals) <= level {
          *vals = append(*vals, []int{root.Val})
      } else {
          (*vals)[level] = append((*vals)[level], root.Val)
      }
      
      dfs(root.Left, level+1, vals)
      dfs(root.Right, level+1, vals)
  }

  展开

   1

   1
• 
  Wade

  2019-03-15

  深度优先搜索， 是中序遍历吗？ 咋感觉好像呢？

  作者回复: 前，中，后序都是深度优先。

  

   1
• 
  塘泥

  2019-12-13

  有没有人写出了非递归的DFS实现？请教

  

  
• 
  GitHubGanKai

  2019-12-10

  请教一个问题 在一个二叉树中 js代码：root === null 和 root.val === null 分别代表着什么意思？在网上有人说，root===null代表当前树不存在，那root.val===null代表什么呢？

  

  
• 
  Aliliin

  2019-11-09

  PHP. 实现：
  递归没写出来。
  function levelOrder1($root)
      {
          if (!$root) return [];
          $res = [];
          $queue = []; // 定义队列 使用数组
          array_push($queue, $root); // 加入根节点
          $level = 0; // 队列里永远存在的是同一个级别的数据，所以要根据级别进行区分是那一层
          while ($queue) { // 只要队列有值就一只循环
              foreach ($queue as $value) {
                  // 它的下一层如果有值的话，就要加入到队列中，
                  if ($value->left != null) array_push($queue, $value->left);
                  if ($value->right != null) array_push($queue, $value->right);
                  // 当前队列中层是有值的，直接就加入进去；
                  $res[$level][] = $value->val;
                  // 这一层处理完了就要删除掉这一层的值
                  array_shift($queue);
              }
              $level++;
          }
          return $res;
      }

  展开

  作者回复: Good!

  

  
• 
  Lugyedo

  2019-09-07

  用深度优先搜索实现二叉树层次遍历，提交都leetcode执行用时 :1 ms, 在所有 Java 提交中击败了100.00%的用户

  

  
• 
  李心宇🦉

  2019-08-03

  没看到go语言版本的，分享一个go语言写的广度优先版本，抛砖引玉。由于go语言没有内置的队列，用单向列表实现了一个简单的队列。
  
  package main
  
  import (
      "fmt"
  )
  
  func main() {
      root := new(treeNode)
      vals := []int{1, 2, 3, 4, 5, 6, 7}
      createBST(vals, root)
      res := resolveLayers(root)
      fmt.Println(res)
  }
  
  // 二叉树节点
  type treeNode struct {
      Val int
      Left *treeNode
      Right *treeNode
  }
  
  // 构造二叉搜索树
  func createBST(vals []int, root *treeNode) {
      pos := len(vals) / 2
      root.Val = vals[pos]
      if pos > 0 {
          root.Left = &treeNode{}
          createBST(vals[:pos], root.Left)
      }
      if pos < len(vals)-1 {
          root.Right = &treeNode{}
          createBST(vals[pos+1:], root.Right)
      }
  }
  
  // 队列元素组成单向链表
  type queueItem struct {
      Val interface{}
      Next *queueItem
  }
  
  // 通过持有队列的首尾元素和长度，更方面的进行入队和出队操作
  type queue struct {
      Len int
      Head *queueItem
      Tail *queueItem
  }
  
  // 入队方法
  func (q *queue) RightPush(item *queueItem) {
      if q.Head == nil || q.Tail == nil {
          q.Head = item
          q.Tail = item
      } else {
          q.Tail.Next = item
          q.Tail = item
      }
      q.Len++
  }
  
  // 出队方法
  func (q *queue) LeftPop() *queueItem {
      if q.Len == 0 {
          return nil
      }
      item := q.Head
      q.Head = q.Head.Next
      if q.Head == nil {
          q.Tail = nil
      }
      q.Len--
      return item
  }
  
  // 分层输出二叉树的节点
  func resolveLayers(root *treeNode) [][]int {
      q := new(queue)
      q.RightPush(&queueItem{Val: root})
      var res [][]int
      for q.Len != 0 {
          thisLen := q.Len
          var layerRes []int
          for i := 0; i < thisLen; i++ {
              node := q.LeftPop().Val.(*treeNode)
              layerRes = append(layerRes, node.Val)
              if node.Left != nil {
                  q.RightPush(&queueItem{Val: node.Left})
                  fmt.Println("left:", node.Left.Val)
              }
              if node.Right != nil {
                  q.RightPush(&queueItem{Val: node.Right})
                  fmt.Println("right:", node.Right.Val)
              }
          }
          res = append(res, layerRes)
      }
      return res
  }
  

  展开

  

  
• 
  the one

  2019-03-26

  java dfs实现：
  
   /**
       * dfs实现
       *
       * @param root
       * @return
       */
      public List<List<Integer>> levelOrderDfs(TreeNode root) {
          List<List<Integer>> res = new ArrayList<>();
          if (root == null) return res;
          _dfs(res, root, 0);
          return res;
      }
  
      void _dfs(List<List<Integer>> res, TreeNode node, int level) {
          if (node == null) return;
          if (res.size() < level + 1) res.add(new ArrayList<>());
          res.get(level).add(node.val);
          _dfs(res, node.left, level + 1);
          _dfs(res, node.right, level + 1);
      }

  展开

  作者回复: Cool!

  

  
• 
  joy

  2019-03-25

  DFS Solution
  /**
   * Definition for a binary tree node.
   * public class TreeNode {
   * int val;
   * TreeNode left;
   * TreeNode right;
   * TreeNode(int x) { val = x; }
   * }
   */
  class Solution {
      public List<List<Integer>> levelOrder(TreeNode root) {
          List<List<Integer>> res = new ArrayList<>();
          levelHelper(res, root, 0);
          return res;
      }
  
      public void levelHelper(List<List<Integer>> res, TreeNode node, int level) {
          if (node == null) return;
          if (res.size() < level + 1) {
              res.add(new ArrayList<>());
          }
          res.get(level).add(node.val);
          levelHelper(res, node.left, level + 1);
          levelHelper(res, node.right, level + 1);
      }
  }

  展开

  作者回复: Nice work

  

  
• 
  Dylan 👻王兴彬

  2019-03-17

  没有用 Swift 来写的小伙伴么？
  BFS，广度优先，算法复杂度 O(n) （Swift）
  ```swift
  /**
   * Definition for a binary tree node.
   * public class TreeNode {
   * public var val: Int
   * public var left: TreeNode?
   * public var right: TreeNode?
   * public init(_ val: Int) {
   * self.val = val
   * self.left = nil
   * self.right = nil
   * }
   * }
   */
  class Solution {
      func levelOrder(_ root: TreeNode?) -> [[Int]] {
          guard let root = root else { return [] }
          
          var result: [[Int]] = []
          var queue: [TreeNode] = []
          queue.append(root)
          
          while !queue.isEmpty {
              let levelSize = queue.count
              var currentLevel: [Int] = []
              
              for _ in 0 ..< levelSize {
                  let node = queue.removeFirst()
                  currentLevel.append(node.val)
                  if let left = node.left {
                      queue.append(left)
                  }
                  if let right = node.right {
                      queue.append(right)
                  }
              }
              
              result.append(currentLevel)
          }
          
          return result
          
      }
  }
  ```

  展开

  作者回复: Cool!

  

  
• 
  Derek

  2019-02-10

  GO语言版本实现：
  
  func levelOrder(root *TreeNode) [][]int {
      var result [][]int
      if root == nil {
          return result
      }
  
      visited := make(map[int]int)
  
      queue := list.New()
      queue.PushBack(root)
  
      for queue.Len() > 0 {
          var curLevel []int
          count := queue.Len()
          for count > 0 {
              element := queue.Front()
              node := element.Value.(*TreeNode)
  
              if _, exist := visited[node.Val]; exist {
                  continue
              }
              visited[node.Val]++
  
              curLevel = append(curLevel, node.Val)
              if node.Left != nil {
                  queue.PushBack(node.Left)
              }
              if node.Right != nil {
                  queue.PushBack(node.Right)
              }
              queue.Remove(element)
              count--
          }
          result = append(result, curLevel)
      }
      return result
  }
  

  展开

  作者回复: 帅！

  

  
• 
  Zu3zz

  2019-02-02

  用c++实现的BFS解
  class Solution {
  public:
      vector<vector<int>> levelOrder(TreeNode* root) {
           // 题目需要返回一个二维数组 二维数组中的每一个元素都是一个一维数组 其中包括了每一层的值
           // 所以提前申明一个二维数组res 用来保存结果
          vector<vector<int>> res;
          // 判断是否为一个空树 如果空树直接返回空二维数组即可
          if(!root) return res;
          // 申明一个队列用来存储二叉树结点值
          queue<TreeNode*> q;
          // 将根节点推入queue中
          q.push(root);
          // 同时添加一个NULL指针用来标记每一层已经走到头
          q.push(NULL);
          // 申明一个数组cur 用来存储每一层的结果 每一层存储完成之后 重置cur
          vector<int> cur;
          // cout<<q.size()<<endl;
          while(!q.empty()){
              // 拿到此时queue中的头结点
              TreeNode *t = q.front();
              // 拿到之后直接队头元素弹出
              q.pop();
              if(t == NULL){
                  // 如果为空指针的话 说明这一层已经走完
                  // 直接将cur数组添加到二维数组res中即可
                  res.push_back(cur);
                  // 将cur重置
                  cur.resize(0);
                  // 如果q的size大于0 说明还没有走到最后一层 接着添加一个NULL指针
                  // 用来标记下一层的结束位置
                  if(q.size()>0){
                      q.push(NULL);
                  }
              }
              else{
                  // 如果不为空 那么说明还有值 直接将val插入cur数组即可
                  cur.push_back(t->val);
                  // 同时如果节点有左子树 右子树 那么将左子树和右子树push进队中 用作下一层的遍历
                  if(t->left){
                      q.push(t->left);
                  }
                  if(t->right){
                      q.push(t->right);
                  }
              }
          }
          return res;
      }
  };

  展开

  作者回复: 帅！

  

  
• 
  翟毅

  2019-01-26

  dfs的思路很棒，以前只知道用队列实现，涨知识

  

  
• 
  2019中国锦鲤

  2018-12-02

  用java实现的深度优先搜索
  public List<List<Integer>> levelOrder(TreeNode root) {
              // 递归的层级
              int level = 0;
              return dfs(root, level, new ArrayList<>());
          }
  
          private List<List<Integer>> dfs(TreeNode root, int level, List<List<Integer>> result) {
              // 递归终止条件，当前节点为空
              if (root == null) {
                  return new ArrayList<>();
              }
              // 如果当前层级没有结果，则新增一个list
              List<Integer> curList;
              if (result.size() == level) {
                  curList = new ArrayList<>();
                  curList.add(root.val);
                  result.add(curList);
              } else {
                  curList = result.get(level);
                  curList.add(root.val);
                  result.set(level, curList);
              }
  
              dfs(root.left, level + 1, result);
              dfs(root.right, level + 1, result);
  
              return result;
          }

  展开

  作者回复: 👍🏻👍🏻

  

  
• 
  yann [扬] :曹同学

  2018-11-28

  >>> res = [[],[]]
  >>> len(res)
  2
  
  dfs里面,级数的判断

  

  
• 
  better man

  2018-11-19

  老师，不用双端队列，直接用队列也可以实现，面试这么写好还是不好

  作者回复: 用队列也可以。一般不用你手动来实现队列。

  

  
• 
  往事随风，顺其自然

  2018-11-10

  用java代码怎么来实现这个，深度优先搜索用java实现没实现出来，老师可以给答案？

  

  
• 
  往事随风，顺其自然

  2018-11-10

  深度优先搜索的Java怎么实现的，实现好久没有实现出来

  

  