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

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); } }

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; }

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); }

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); } }

没有用 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 } } ```

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 }

用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; } };

用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; }

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