V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Acceml
V2EX  ›  程序员

[Leetcode] 102. 二叉树的层次遍历

  •  
  •   Acceml ·
    Acceml · 2019-02-26 08:09:07 +08:00 · 2839 次点击
    这是一个创建于 2082 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

    给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

    例如: 给定二叉树: [3,9,20,null,null,15,7],

        3
       / \
      9  20
        /  \
       15   7
    

    返回其层次遍历结果:

    [
      [3],
      [9,20],
      [15,7]
    ]
    

    题解

    我们数据结构的书上教的层序遍历,就是利用一个队列,不断的把左子树和右子树入队。但是这个题目还要要求按照层输出。所以关键的问题是: 如何确定是在同一层的。 我们很自然的想到: 如果在入队之前,把上一层所有的节点出队,那么出队的这些节点就是上一层的列表。 由于队列是先进先出的数据结构,所以这个列表是从左到右的。

    /**
     * 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 LinkedList<>();
            if (root == null) {
                return res;
            }
    
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                int size = queue.size();
                List<Integer> currentRes = new LinkedList<>();
                // 当前队列的大小就是上一层的节点个数, 依次出队
                while (size > 0) {
                    TreeNode current = queue.poll();
                    if (current == null) {
                        continue;
                    }
                    currentRes.add(current.val);
                    // 左子树和右子树入队.
                    if (current.left != null) {
                        queue.add(current.left);
                    }
                    if (current.right != null) {
                        queue.add(current.right);
                    }
                    size--;
                }
                res.add(currentRes);
            }
            return res;
        }
    }
    

    这道题可不可以用非递归来解呢?

    递归的子问题:遍历当前节点, 对于当前层, 遍历左子树的下一层层,遍历右子树的下一层

    递归结束条件: 当前层,当前子树节点是 null

    /**
     * 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 LinkedList<>();
            if (root == null) {
                return res;
            }
            levelOrderHelper(res, root, 0);
            return res;
        }
    
        /**
         * @param depth 二叉树的深度
         */
        private void levelOrderHelper(List<List<Integer>> res, TreeNode root, int depth) {
            if (root == null) {
                return;
            }
            
            if (res.size() <= depth) {
                // 当前层的第一个节点,需要 new 一个 list 来存当前层.
                res.add(new LinkedList<>());
            }
            // depth 层,把当前节点加入
            res.get(depth).add(root.val);
            // 递归的遍历下一层.
            levelOrderHelper(res, root.left, depth + 1);
            levelOrderHelper(res, root.right, depth + 1);
        }
    }
    

    热门阅读

    Leetcode 名企之路

    8 条回复    2019-02-27 08:36:09 +08:00
    8a9a09dw12
        1
    8a9a09dw12  
       2019-02-26 09:44:00 +08:00
    现在去 leetcode 上写个二叉树遍历也可以拿出来的吹了吗?
    JasonSi
        2
    JasonSi  
       2019-02-26 09:49:46 +08:00   ❤️ 1
    @8a9a09dw12 说明你不是目标用户( doge
    8a9a09dw12
        3
    8a9a09dw12  
       2019-02-26 09:55:04 +08:00
    @JasonSi 垃圾营销号真的恶心
    Bryan0Z
        4
    Bryan0Z  
       2019-02-26 10:25:32 +08:00 via Android
    道理我都懂,不就是 BFS 嘛…
    holy_sin
        5
    holy_sin  
       2019-02-26 10:36:58 +08:00
    老铁 这是要连发 900 帖吗
    11232as
        6
    11232as  
       2019-02-26 10:39:38 +08:00
    这不是数据结构基础???
    mskf
        7
    mskf  
       2019-02-26 10:41:42 +08:00
    上面用队列的非递归,下面是递归,那你中间一句话有问题啊,啥叫 这道题可不可以用非递归来解呢?
    20015jjw
        8
    20015jjw  
       2019-02-27 08:36:09 +08:00 via Android
    @mskf hhhhh 我没仔细看以为 lz 已经变强了 没想到喷点还是这么多

    lz 你这水平到底是怎么面过名企的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   935 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 21:53 · PVG 05:53 · LAX 13:53 · JFK 16:53
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.