大家好，我是小魔龍，Unity3D軟體工程師，VR、AR，虛拟仿真方向，不定時更新軟體開發技巧，生活感悟，覺得有用記得一鍵三連哦。
一、題目
1、算法題目
“給定二叉樹根節點，傳回節點值自底向上的層序周遊。”
題目連結：
來源：力扣（LeetCode）
連結：107. 二叉樹的層序周遊 II - 力扣（LeetCode） (leetcode-cn.com)
2、題目描述
給你二叉樹的根節點
root
，傳回其節點值 自底向上的層序周遊 。 （即按從葉子節點所在層到根節點所在的層，逐層從左向右周遊）。
示例 1：
輸入： root = [3,9,20,null,null,15,7]
輸出： [[15,7],[9,20],[3]] 複制
示例 2：
輸入： root = [1]
輸出： [[1]] 複制
二、解題
1、思路分析
這道題和102題二叉樹的層序周遊類似，不同的地方在于102題要求從上到下輸出每一層的節點值。
這一題是從下到上輸出每一層的節點值。
雖然說輸出順序不同，但是思路是相同的，都可以使用廣度優先搜尋記性層次周遊。
從根節點開始搜尋，每次周遊同一層的全部節點，使用清單存儲改層的節點值。
在周遊完一層節點之後，将存儲該層節點值的清單添加到結果清單的頭部。
2、代碼實作
代碼參考：
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);
TreeNode left = node.left, right = node.right;
if (left != null) {
queue.offer(left);
}
if (right != null) {
queue.offer(right);
}
}
levelOrder.add(0, level);
}
return levelOrder;
}
} 複制
3、時間複雜度
時間複雜度 ： O(n)
其中n是樹中的節點個數。每個節點通路一次，結果清單使用連結清單的結構，在結構清單頭部添加一層節點值的清單的時間複雜度為O(1)，是以總時間複雜度為O(n)。
空間複雜度： O(n)
其中n是樹中的節點個數。
三、總結
為了降低在結果清單頭部添加一層節點值的清單的時間複雜度，結果清單可以使用連結清單的結構。
在代碼中，需要傳回List類型的資料，可以使用連結清單實作。