LeetCode–二叉樹的層次遍歷 II
博客說明
文章所涉及的資料來自互聯網整理和個人總結，意在于個人學習和經驗匯總，如有什么地方侵權，請聯系本人洗掉，謝謝！
介紹
107. 二叉樹的層次遍歷 II
題目
給定一個二叉樹，回傳其節點值自底向上的層次遍歷， （即按從葉子節點所在層到根節點所在的層，逐層從左向右遍歷）
例如：
給定二叉樹 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
回傳其自底向上的層次遍歷為：
[
[15,7],
[9,20],
[3]
]
思路
廣度優先搜索
-
樹的層次遍歷可以使用廣度優先搜索實作，從根節點開始搜索，每次遍歷同一層的全部節點，使用一個串列存盤該層的節點值
-
如果要求從上到下輸出每一層的節點值，做法是很直觀的，在遍歷完一層節點之后，將存盤該層節點值的串列添加到結果串列的尾部，這道題要求從下到上輸出每一層的節點值，只要對上述操作稍作修改即可：在遍歷完一層節點之后，將存盤該層節點值的串列添加到結果串列的頭部
代碼
/**
* 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>> levelOrderBottom(TreeNode root) {
//結果
List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
if(root == null){
return levelOrder;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
//廣度搜索
while(!queue.isEmpty()){
List<Integer> level = new ArrayList<Integer>();
int size = queue.size();
for(int i = 0; i < size; i++){
TreeNode node = queue.poll();
level.add(node.val);
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
//每次都插入到第一個位置
levelOrder.add(0,level);
}
return levelOrder;
}
}
感謝
Leetcode
以及勤勞的自己，個人博客，GitHub
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/1917.html
標籤：Java