【問(wèn)題描述】[第102題][二叉樹(shù)的層序遍歷][中等]

給你一個(gè)二叉樹(shù)，請(qǐng)你返回其按 層序遍歷 得到的節(jié)點(diǎn)值。 （即逐層地，從左到右訪問(wèn)所有節(jié)點(diǎn)）。示例： 二叉樹(shù)：[3,9,20,null,null,15,7],3/ \9 20/ \15 7 返回其層次遍歷結(jié)果：[[3],[9,20],[15,7] ]

【解答思路】

典型BFS

1.隊(duì)列

• 一層一層入隊(duì)，統(tǒng)計(jì)每層數(shù)量
• 當(dāng)前層出隊(duì)，下一層入隊(duì)
  時(shí)間復(fù)雜度：O(N^2) 空間復(fù)雜度：O(1)

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) return res;Deque<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {List<Integer> tmp = new ArrayList<>();//每一層的數(shù)量int cnt = queue.size();for (int i = 0; i < cnt; i++) {TreeNode node = queue.poll();// System.out.println(node.val);tmp.add(node.val);if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}//所有出完之后 添加listres.add(tmp);}return res;} }

2. 遞歸

helper(res, root, 0);
0代表層數(shù) 也代表列表的下標(biāo)
時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(1)

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();helper(res, root, 0);return res;}private void helper(List<List<Integer>> res, TreeNode root, int depth) {if (root == null) return;if (res.size() == depth) res.add(new LinkedList<>());res.get(depth).add(root.val);helper(res, root.left, depth + 1);helper(res, root.right, depth + 1);} }

【總結(jié)】

1.模板

DFS 遍歷使用遞歸

void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);dfs(root.right); }

BFS遍歷使用模板（層次遍歷 最短路徑）

void bfs(TreeNode root) {Queue<TreeNode> queue = new ArrayDeque<>();queue.add(root);while (!queue.isEmpty()) {TreeNode node = queue.poll(); // Java 的 pop 寫(xiě)作 poll()if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}} }

2.二叉樹(shù)遍歷

前序遍歷 先輸出當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)，再依次遍歷輸出左結(jié)點(diǎn)和右結(jié)點(diǎn)
中序遍歷 先遍歷輸出左結(jié)點(diǎn)，再輸出當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)，再遍歷輸出右結(jié)點(diǎn)
后續(xù)遍歷 先遍歷輸出左結(jié)點(diǎn)，再遍歷輸出右結(jié)點(diǎn)，最后輸出當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)

參考鏈接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/di-gui-he-die-dai-by-powcai-2/

總結(jié)

以上是生活随笔為你收集整理的[Leedcode][JAVA][第102题][二叉树的层序遍历][递归][迭代][BFS]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。