1. 首页
  2. Leetcode经典148题

leetcode-102-Binary-Tree-Level-Order-Traversal

题目描述(中等难度)

leetcode-102-Binary-Tree-Level-Order-Traversal

二叉树的层次遍历,输出一个 list 的 list。

解法一 DFS

这道题考的就是 BFS,我们可以通过 DFS 实现。只需要在递归过程中将当前 level 传入即可。

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>(); 
    DFS(root, 0, ans);
    return ans;
}

private void DFS(TreeNode root, int level, List<List<Integer>> ans) {
    if(root == null){
        return;
    }
    //当前层数还没有元素,先 new 一个空的列表
    if(ans.size()<=level){
        ans.add(new ArrayList<>());
    }
    //当前值加入
    ans.get(level).add(root.val);

    DFS(root.left,level+1,ans);
    DFS(root.right,level+1,ans);
}

解法二 BFS 队列

如果是顺序刷题,前边的 “> 98 题public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); if (root == null) { return ans; } Queue<TreeNode> treeNode = new LinkedList<>(); Queue<Integer> nodeLevel = new LinkedList<>(); treeNode.offer(root); int level = 0; nodeLevel.offer(level); while (!treeNode.isEmpty()) { TreeNode curNode = treeNode.poll(); int curLevel = nodeLevel.poll(); if (curNode != null) { if (ans.size() <= curLevel) { ans.add(new ArrayList<>()); } ans.get(curLevel).add(curNode.val); level = curLevel + 1; treeNode.offer(curNode.left); nodeLevel.offer(level); treeNode.offer(curNode.right); nodeLevel.offer(level); } } return ans; }

方案二

参考public List<List<Integer>> levelOrder(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); List<List<Integer>> ans = new LinkedList<List<Integer>>(); if (root == null) return ans; queue.offer(root); while (!queue.isEmpty()) { int levelNum = queue.size(); // 当前层元素的个数 List<Integer> subList = new LinkedList<Integer>(); for (int i = 0; i < levelNum; i++) { TreeNode curNode = queue.poll(); if (curNode != null) { subList.add(curNode.val); queue.offer(curNode.left); queue.offer(curNode.right); } } if(subList.size()>0){ ans.add(subList); } } return ans; }

考察的知识点就是二叉树的 BFS,解法二的方案二是自己不曾想到的, while 循环中加入一个 for 循环,很妙!

作者:windliang

来源:https://windliang.cc

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:leetcode-102-Binary-Tree-Level-Order-Traversal

链接:https://www.javajike.com/article/3239.html

« leetcode-101-Symmetric-Tree
leetcode-103-Binary-Tree-Zigzag-Level-Order-Traversal»

相关推荐

QR code