当前播放: 28 | 面试题:二叉树层次遍历
00:00 / 00:00
高清
  • 高清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看
课程目录
第一章:课程综述 (4讲)
01 | 合格程序员的第一步:算法与数据结构
免费
02 | 如何事半功倍地学习算法与数据结构
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算法题目练习
免费
第二章:理论讲解+面试题实战 (53讲)
05 | 理论讲解:数组&链表
免费
06 | 面试题:反转一个单链表&判断链表是否有环
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是否有效
09 | 面试题:用队列实现栈&用栈实现队列
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第K大元素
12 | 面试题:返回滑动窗口中的最大值
13 | 理论讲解:哈希表
14 | 面试题:有效的字母异位词
15 | 面试题:两数之和
16 | 面试题:三数之和
17 | 理论讲解:树&二叉树&二叉搜索树
18 | 面试题:验证二叉搜索树
19 | 面试题:二叉树&二叉搜索树的最近公共祖先
20 | 理论讲解:二叉树遍历
21 | 理论讲解:递归&分治
22 | 面试题:Pow(x,n)
23 | 面试题:求众数
24 | 理论讲解:贪心算法
25 | 面试题:买卖股票的最佳时机
26 | 理论讲解:广度优先搜索
27 | 理论讲解:深度优先搜索
28 | 面试题:二叉树层次遍历
29 | 面试题:二叉树的最大和最小深度
30 | 面试题:生成有效括号组合
31 | 理论讲解:剪枝
32 | 面试题:N皇后问题
33 | 面试题:数独问题
34 | 理论讲解:二分查找
35 | 面试题:实现一个求解平方根的函数
36 | 理论讲解:字典树
37 | 面试题:实现一个字典树
38 | 面试题:二维网格中的单词搜索问题
39 | 理论讲解:位运算
40 | 面试题:统计位1的个数
41 | 面试题:2的幂次方问题&比特位计数问题
42 | 面试题:N皇后问题的另一种解法
43 | 理论理解:动态规划(上)
44 | 理论理解:动态规划(下)
45 | 面试题:爬楼梯
46 | 面试题:三角形的最小路径和
47 | 面试题:乘积最大子序列
48 | 面试题:股票买卖系列
49 | 面试题:最长上升子序列
50 | 面试题:零钱兑换
51 | 面试题:编辑距离
52 | 理论讲解:并查集
53 | 面试题:岛屿的个数&朋友圈(上)
54 | 面试题:岛屿的个数&朋友圈(下)
55 | 理论讲解: LRU Cache
56 | 面试题:设计和实现一个LRU Cache缓存机制
57 | 理论讲解:布隆过滤器
第三章:课程总结 (5讲)
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件套
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契数列
62 | 结课测试&最后的一些经验分享
28 | 面试题:二叉树层次遍历

28 | 面试题:二叉树层次遍历

覃超
Sophon Tech创始人,前Facebook工程师,卡内基梅隆大学计算机硕士
全集24347
新人首单 ¥29.9 原价 ¥129
35
登录 后留言

精选留言(25)

  • Wade
    深度优先搜索, 是中序遍历吗? 咋感觉好像呢?

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

    2019-03-15
    5
  • 涂改
    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);
        }
    }

    作者回复: 帅!!

    2019-03-02
    1
    4
  • polk
    照着深度优先把之前那个股票的题目暴力解决了
    2020-03-08
    1
  • mickey
    DFS:

    class Solution2 {
    public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if (root == null)
    return res;
    _levelOrder(root, 0, res);
    return res;

    }

    private void _levelOrder(TreeNode node, int level, List<List<Integer>> res) {
    if (node == null)
    return;

    if (res.size() < level + 1)
    res.add(new ArrayList<Integer>());

    res.get(level).add(node.val);

    _levelOrder(node.left, level + 1, res);
    _levelOrder(node.right, level + 1, res);
    }
    }
    2020-03-05
    1
  • 李心宇🦉
    没看到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
    }
    2019-08-03
    1
  • Alexdown
    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)
    }
    2019-06-19
    1
    1
  • 剑八
    public List<List<Integer>> levelOrder(TreeNode root) {
            if (root == null) {
                return new ArrayList<>();
            }

            Deque<TreeNode> queue = new LinkedList();
            List<List<Integer>> rList = new ArrayList<>();
            queue.add(root);

            rList.add(Arrays.asList(root.val));

            //4,3,2
            while (!queue.isEmpty()) {
                List<Integer> tList = iterate(queue);
                if (tList != null && !tList.isEmpty()) {
                    rList.add(tList);
                }
            }
            return rList;
        }

        private List<Integer> iterate(Deque<TreeNode> queue) {
            if (queue == null) {
                return null;
            }

            /**
             * 遍历queue中这层结点
             */
            List<Integer> rList = new ArrayList<>();

            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = queue.pollFirst();
                List<Integer> tList = getListNodeOfChild(treeNode);
                if (tList != null && !tList.isEmpty()) {
                    rList.addAll(tList);
                }
                if (treeNode.left != null) {
                    queue.offerLast(treeNode.left);
                }
                if (treeNode.right != null) {
                    queue.offerLast(treeNode.right);
                }
            }
            return rList;
        }

        private List<Integer> getListNodeOfChild(TreeNode treeNode) {
            if (treeNode == null) {
                return null;
            }
            if (treeNode.left == null && treeNode.right == null) {
                return null;
            }
            List<Integer> tList = new ArrayList<>();
            if (treeNode.left != null) {
                tList.add(treeNode.left.val);
            }
            if (treeNode.right != null) {
                tList.add(treeNode.right.val);
            }
            return tList;
        }
    2020-07-26
  • 肖家文
    贴一份C语言的实现:
    /**
     * Return an array of arrays of size *returnSize.
     * The sizes of the arrays are returned as *returnColumnSizes array.
     * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
     */
    int **levelOrder(struct TreeNode *root, int *returnSize, int **returnColumnSizes)
    {
        if (!root) {
            *returnSize = 0;
            *returnColumnSizes = NULL;
            return NULL;
        }
        int **results = malloc(sizeof(int *)*MAX_LEVEL);
        int *ret_column_size = malloc(sizeof(int) * MAX_LEVEL);
        int result_index = 0;
        struct TreeNode *queue[MAX_QUEUE_LEN];
        int queue_left = 0;
        int queue_right = 0;
        queue[queue_right++] = root;

        while (queue_right != queue_left) {
            int level = result_index;
            int level_size = (queue_right - queue_left + MAX_QUEUE_LEN) % MAX_QUEUE_LEN;
            ret_column_size[level] = level_size;
            results[result_index++] = malloc(sizeof(int) * level_size);
            for (int i = 0; i < level_size; i++) {
                results[level][i] = queue[queue_left]->val;
                if (queue[queue_left]->left) {
                    queue[queue_right] = queue[queue_left]->left;
                    queue_right = (queue_right + 1) % MAX_QUEUE_LEN;
                }
                if (queue[queue_left]->right) {
                    queue[queue_right] = queue[queue_left]->right;
                    queue_right = (queue_right + 1) % MAX_QUEUE_LEN;
                }
                queue_left = (queue_left + 1) % MAX_QUEUE_LEN;
            }
        }
        *returnColumnSizes = ret_column_size;
        *returnSize = result_index;
        return results;
    }
    2020-05-17
  • Season
    Golang实现的BFS,由于Golang中没有双端队列,因此使用两个数据来代替。
    func levelOrder(root *TreeNode) [][]int {

    var result [][]int

    if root == nil {
    return result
    }

    var q = []*TreeNode{root}

    for len(q) > 0 {
    var current []int
    var p []*TreeNode
    for _, v := range q {
    current = append(current, v.Val)
    if v.Left != nil {
    p = append(p, v.Left)
    }
    if v.Right != nil {
    p = append(p, v.Right)
    }
    }
    result = append(result, current)
    q = p
    }

    return result
    }
    2019-12-30
  • lzh
    一个queue区分每层分界比较困难,那就用两个queue,每层元素交替放置在queue中

    原创,C++:

    class Solution {
    public:
    vector<vector<int>> levelOrder(TreeNode* root) {
    if (root == NULL)
    {
    return (vector<vector<int>>)NULL;
    }

    this->q1->push(root);
    this->is_q1 = true;

    while (!this->q1->empty() || !this->q2->empty())
    {
    this->is_q1 ? this->doWork(this->q1, this->q2) : this->doWork(this->q2, this->q1);
    }

    return *(this->result);
    }
    private:
    queue<TreeNode*> *q1 = new queue<TreeNode*>;
    queue<TreeNode*> *q2 = new queue<TreeNode*>;
    vector<int> *row = new vector<int>;
    vector<vector<int>> *result = new vector<vector<int>>;
    bool is_q1;

    void doWork(queue<TreeNode*> *pop, queue<TreeNode*> *push)
    {
    TreeNode *node = NULL;

    if (!pop->empty())
    {
    node = pop->front();
    if (node->left != NULL)
    {
    push->push(node->left);
    }
    if (node->right != NULL)
    {
    push->push(node->right);
    }
    this->row->push_back(node->val);
    pop->pop();
    }
    if (pop->empty())
    {
    this->result->push_back(*(this->row));
    this->row = new vector<int>;
    this->is_q1 = !this->is_q1;
    }
    }
    };
    2019-12-26
  • 塘泥
    有没有人写出了非递归的DFS实现?请教
    2019-12-13
  • GitHubGanKai
    请教一个问题 在一个二叉树中 js代码:root === null 和 root.val === null 分别代表着什么意思?在网上有人说,root===null代表当前树不存在,那root.val===null代表什么呢?
    2019-12-10
  • Aliliin
    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!

    2019-11-09
    2
  • Lugyedo
    用深度优先搜索实现二叉树层次遍历,提交都leetcode执行用时 :1 ms, 在所有 Java 提交中击败了100.00%的用户
    2019-09-07
  • the one
    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!

    2019-03-26
  • joy
    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

    2019-03-25
  • 棒棒彬👻
    没有用 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!

    2019-03-17
  • Derek
    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
    }

    作者回复: 帅!

    2019-02-10
  • Zu3zz
    用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-02-02
  • 翟毅
    dfs的思路很棒,以前只知道用队列实现,涨知识
    2019-01-26
收起评论
看过的人还看
数据结构与算法之美

王争  前Google工程师

80讲 | 90175 人已学习

新人首单 ¥29.9 原价 ¥129
趣谈网络协议

刘超  网易研究院云计算技术部首席架构师

51讲 | 46023 人已学习

新人首单 ¥19.9 原价 ¥99
左耳听风

陈皓  网名“左耳朵耗子”,资深技术专家,骨灰级程序员

109讲 | 46630 人已学习

新人首单 ¥69.9 原价 ¥299
Java核心技术面试精讲

杨晓峰  前Oracle首席工程师

44讲 | 47447 人已学习

新人首单 ¥19.9 原价 ¥99