leetcode 二叉樹相關-層序遍歷專題

二叉樹的層序遍歷一般來說，我們是利用隊列來實現的，先把根節點入隊，然后在出隊后將其對應的子節點入隊，然后往復此種操作。相比于二叉樹的遍歷遞歸，層序遍歷比較簡單，有些題目用想不出遞歸的解法，用層序遍歷也是可以解答。我個人覺得層序遍歷可以按照這個模板：

class Solution {public void levelOrder(TreeNode root) {Queue<TreeNode> q = new LinkedList<>();q.offer(root);while (!q.isEmpty()) {int sz = q.size();while (sz-- > 0) {TreeNode node = q.poll();if (node.left != null) q.offer(node.left);if (node.right != null) q.offer(node.right);}}}
}

下面以leetcode上的相關題目來解答

leecode 102 二叉樹的層序遍歷

題目鏈接 ：https://leetcode.cn/problems/binary-tree-level-order-traversal/description/

題目

給你二叉樹的根節點 root ，返回其節點值的 層序遍歷 。 （即逐層地，從左到右訪問所有節點）。

示例 1：
輸入：root = [3,9,20,null,null,15,7]
輸出：[[3],[9,20],[15,7]]

示例 2：
輸入：root = [1]
輸出：[[1]]

示例 3：
輸入：root = []
輸出：[]

提示：
樹中節點數目在范圍 [0, 2000] 內
-1000 <= Node.val <= 1000

解題思路

直接套模板解答

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) return res;Queue<TreeNode> q = new LinkedList<>();q.offer(root);while (!q.isEmpty()) {int sz = q.size();List<Integer> tmp = new ArrayList<>();while (sz-- > 0) {TreeNode node = q.poll();tmp.add(node.val);if (node.left != null) q.offer(node.left);if (node.right != null) q.offer(node.right);}res.add(new ArrayList<>(tmp));}return res;}
}

leecode 107 二叉樹的層序遍歷||

題目鏈接 ：https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/description/

題目

給你二叉樹的根節點 root ，返回其節點值 自底向上的層序遍歷 。 （即按從葉子節點所在層到根節點所在的層，逐層從左向右遍歷）

示例 1：
輸入：root = [3,9,20,null,null,15,7]
輸出：[[15,7],[9,20],[3]]

示例 2：
輸入：root = [1]
輸出：[[1]]

示例 3：
輸入：root = []
輸出：[]

提示：
樹中節點數目在范圍 [0, 2000] 內
-1000 <= Node.val <= 1000

解題思路

相當于是在leetcode102的解答上對結果進行翻轉

class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) return res;Deque<TreeNode> q = new LinkedList<>();q.offer(root);while (!q.isEmpty()) {int sz = q.size();List<Integer> path = new ArrayList<>();while (sz > 0) {TreeNode node = q.poll();path.add(node.val);if (node.left != null) q.offer(node.left);if (node.right != null) q.offer(node.right);sz--;}res.add(path);}List<List<Integer>> result = new ArrayList<>();for (int i = res.size() - 1; i >=0 ; i--) { //翻轉result.add(res.get(i));}return result;}
}

leecode 199 二叉樹的右視圖

題目鏈接 ：https://leetcode.cn/problems/binary-tree-right-side-view/description/

題目

給定一個二叉樹的 根節點 root，想象自己站在它的右側，按照從頂部到底部的順序，返回從右側所能看到的節點值。

示例 1:

輸入: [1,2,3,null,5,null,4]
輸出: [1,3,4]

示例 2:
輸入: [1,null,3]
輸出: [1,3]

示例 3:
輸入: []
輸出: []

提示:
二叉樹的節點個數的范圍是 [0,100]
-100 <= Node.val <= 100

解題思路

還是直接套模板，就是在當層隊列大小取出最后一個節點的時候進行處理。

class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) return res;Deque<TreeNode> q = new LinkedList<>();q.offer(root);while (!q.isEmpty()) {int sz = q.size();for (int i = 0; i < sz; i++) {TreeNode node = q.poll();if (node.left != null) q.offer(node.left);if (node.right != null) q.offer(node.right);if (i == sz - 1) {res.add(node.val);}}}return res;}
}

leecode 637 二叉樹的層平均值

題目鏈接 ：https://leetcode.cn/problems/average-of-levels-in-binary-tree/description/

題目

給定一個非空二叉樹的根節點 root , 以數組的形式返回每一層節點的平均值。與實際答案相差 10-5 以內的答案可以被接受。

示例 1：

輸入：root = [3,9,20,null,null,15,7]
輸出：[3.00000,14.50000,11.00000]
解釋：第 0 層的平均值為 3,第 1 層的平均值為 14.5,第 2 層的平均值為 11 。
因此返回 [3, 14.5, 11] 。

示例 2:

輸入：root = [3,9,20,15,7]
輸出：[3.00000,14.50000,11.00000]

提示：
樹中節點數量在 [1, 104] 范圍內
-231 <= Node.val <= 231 - 1

解題思路

直接套模板解答，在當成節點處理完后，計算并記錄其平均值

class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> res = new ArrayList<>();if (root == null) return res;Deque<TreeNode> q = new LinkedList<>();q.offer(root);while (!q.isEmpty()) {int sz = q.size();double sum = 0;for (int i = 0; i < sz; i++) {TreeNode node = q.poll();sum += node.val;if (node.left != null) q.offer(node.left);if (node.right != null) q.offer(node.right);}res.add(sum / sz);}return res;}
}

還有一些相關題目也是在模板基礎上進行處理，后續看情況出第二遍層序遍歷題目專題。