石家莊做網(wǎng)站seo宣傳鏈接怎么做
一、題目描述
給你二叉樹的根節(jié)點(diǎn) root ，返回其節(jié)點(diǎn)值 自底向上的層序遍歷 。 （即按從葉子節(jié)點(diǎn)所在層到根節(jié)點(diǎn)所在的層，逐層從左向右遍歷）
示例 1：
輸入：root = [3,9,20,null,null,15,7] 輸出：[[15,7],[9,20],[3]]
示例 2：
輸入：root = [1] 輸出：[[1]]
示例 3：
輸入：root = [] 輸出：[]
提示：
- 樹中節(jié)點(diǎn)數(shù)目在范圍
[0, 2000]內(nèi) -1000 <= Node.val <= 1000
二、解題思路
?這個問題是關(guān)于如何對二叉樹進(jìn)行自底向上的層序遍歷。我們可以使用一個隊(duì)列來進(jìn)行廣度優(yōu)先搜索（BFS），并使用一個變量來記錄當(dāng)前層的節(jié)點(diǎn)值。在遍歷每一層的時候，我們使用一個雙端隊(duì)列（Deque）來存儲當(dāng)前層的節(jié)點(diǎn)值，這樣我們就可以從雙端隊(duì)列的尾部開始遍歷，從而實(shí)現(xiàn)自底向上的層序遍歷。
算法步驟：
- 初始化一個空隊(duì)列
queue用于BFS，以及一個空的雙端隊(duì)列deque用于存儲當(dāng)前層的節(jié)點(diǎn)值。 - 如果
root不為空，則將其加入queue。 - 初始化一個變量
level為0，用于標(biāo)識當(dāng)前層的奇偶性。 - 當(dāng)
queue不為空時，進(jìn)行以下操作：?a. 獲取當(dāng)前層的節(jié)點(diǎn)數(shù)量size（即queue的長度）。?b. 遍歷當(dāng)前層的節(jié)點(diǎn)，對于每個節(jié)點(diǎn)：?i. 從queue中移除節(jié)點(diǎn)，并將其值加入deque的頭部（如果level為偶數(shù)）或尾部（如果level為奇數(shù)）。?ii. 如果該節(jié)點(diǎn)的左子節(jié)點(diǎn)不為空，將其加入queue。?iii. 如果該節(jié)點(diǎn)的右子節(jié)點(diǎn)不為空，將其加入queue。?c. 將deque轉(zhuǎn)換為列表，并加入結(jié)果列表result。?d. 將level加1，清空deque。 - 返回結(jié)果列表
result。
三、具體代碼
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;public class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) {return result;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int level = 0;while (!queue.isEmpty()) {int size = queue.size();Deque<Integer> deque = new LinkedList<>();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (node != null) {deque.offerLast(node.val);queue.offer(node.left);queue.offer(node.right);}}if (!deque.isEmpty()) {result.add(0, new ArrayList<>(deque));}}return result;}
}
四、時間復(fù)雜度和空間復(fù)雜度
1. 時間復(fù)雜度
levelOrderBottom?函數(shù)會對每個節(jié)點(diǎn)進(jìn)行一次操作，其中?n?是樹中節(jié)點(diǎn)的數(shù)量。- 因此，總的時間復(fù)雜度是 O(n)。
2. 空間復(fù)雜度
- 空間復(fù)雜度主要取決于隊(duì)列和雙端隊(duì)列中存儲的節(jié)點(diǎn)數(shù)量。
- 在最壞的情況下，樹是完全不平衡的，例如每個節(jié)點(diǎn)都只有左子節(jié)點(diǎn)或者只有右子節(jié)點(diǎn)，此時隊(duì)列和雙端隊(duì)列中存儲的節(jié)點(diǎn)數(shù)量最多，為 O(n)。
- 因此，總的空間復(fù)雜度是 O(n)。
綜上所述，代碼的時間復(fù)雜度是 O(n)，空間復(fù)雜度也是 O(n)，其中 n 是樹中節(jié)點(diǎn)的數(shù)量。
五、總結(jié)知識點(diǎn)
-
隊(duì)列（Queue）的使用：代碼中使用了
LinkedList類作為Queue的實(shí)現(xiàn)，用于在BFS中存儲待遍歷的節(jié)點(diǎn)。隊(duì)列遵循先進(jìn)先出（FIFO）的原則。 -
遞歸：雖然代碼中沒有直接使用遞歸，但BFS本質(zhì)上是一種遞歸的過程，通過循環(huán)模擬遞歸的調(diào)用棧。
-
雙端隊(duì)列（Deque）的使用：代碼中使用了
LinkedList類作為Deque的實(shí)現(xiàn)，用于在每一層遍歷時存儲當(dāng)前層的節(jié)點(diǎn)值。雙端隊(duì)列可以同時從兩端添加或刪除元素。 -
迭代與循環(huán)：使用
while循環(huán)來迭代遍歷樹的每一層，直到隊(duì)列為空。 -
條件語句：使用
if-else語句來判斷節(jié)點(diǎn)是否為空，以及判斷隊(duì)列是否為空。 -
數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換：使用
ArrayList和LinkedList之間的轉(zhuǎn)換，將Deque中的元素轉(zhuǎn)換為一個List，然后添加到結(jié)果List中。 -
布爾變量的使用：使用布爾變量
level來標(biāo)志當(dāng)前層的奇偶性，并在每層遍歷后取反。 -
樹節(jié)點(diǎn)的定義：代碼中使用了
TreeNode類來定義二叉樹的節(jié)點(diǎn)，每個節(jié)點(diǎn)包含一個整數(shù)值和指向左右子節(jié)點(diǎn)的引用。 -
函數(shù)返回值：
levelOrderBottom函數(shù)返回一個包含多層的List<List<Integer>>，表示二叉樹的自底向上的層序遍歷結(jié)果。 -
邊界條件的處理：在函數(shù)開始時檢查
root是否為空，如果為空則直接返回一個空列表。
以上就是解決這個問題的詳細(xì)步驟，希望能夠?yàn)楦魑惶峁﹩l(fā)和幫助。