一、題目描述
給你二叉樹的根節點?root?，返回它節點值的?前序?遍歷。
示例 1：
輸入：root = [1,null,2,3] 輸出：[1,2,3]
示例 2：
輸入：root = [] 輸出：[]
示例 3：
輸入：root = [1] 輸出：[1]
示例 4：
輸入：root = [1,2] 輸出：[1,2]
示例 5：
輸入：root = [1,null,2] 輸出：[1,2]
提示：
- 樹中節點數目在范圍?
[0, 100]?內 -100 <= Node.val <= 100
二、方法一：遞歸方法
（一）解題思路
遞歸方法是最直觀的，按照前序遍歷的順序，遞歸地訪問每個節點：
- 如果當前節點為空，返回。
- 訪問當前節點，將節點的值添加到結果列表中。
- 遞歸地前序遍歷左子樹。
- 遞歸地前序遍歷右子樹。
（二）具體代碼
import java.util.ArrayList;
import java.util.List;public class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();preorder(root, result);return result;}private void preorder(TreeNode node, List<Integer> result) {if (node == null) {return;}result.add(node.val); // 訪問根節點preorder(node.left, result); // 遍歷左子樹preorder(node.right, result); // 遍歷右子樹}
}
（三）時間復雜度和空間復雜度
1. 時間復雜度
- 原因：遞歸方法訪問樹中每個節點一次。
- 計算：對于具有
N個節點的二叉樹，每個節點都恰好被訪問一次。 - 結果：時間復雜度為
O(N)，其中N是二叉樹中節點的數量。
2. 空間復雜度
- 原因：遞歸方法使用棧空間來存儲遞歸調用的信息，其大小取決于樹的高度。
- 最壞情況：如果樹完全不平衡，每個節點只有左子節點或只有右子節點，遞歸棧的深度將達到
N。 - 最好情況：如果樹是完全平衡的，遞歸棧的深度將是
logN。 - 額外空間：代碼中沒有使用除了遞歸棧以外的額外空間。
- 結果：空間復雜度介于
O(logN)和O(N)之間，取決于樹的形狀。額外空間復雜度是O(1)。
3. 總結
- 時間復雜度：
O(N) - 空間復雜度：
O(1)（額外空間），O(logN)到O(N)（遞歸棧空間）
（四）總結知識點
-
遞歸：這是一種編程技巧，允許函數調用自身。在這個代碼中，
preorder函數會遞歸地調用自身來遍歷二叉樹的每個節點。 -
二叉樹遍歷：代碼實現了二叉樹的前序遍歷，這是一種深度優先遍歷策略，按照“根-左-右”的順序訪問樹的節點。
-
二叉樹節點定義：代碼中使用了
TreeNode類來定義二叉樹的節點，每個節點包含一個整數值val和兩個指向其左右子節點的指針left和right。 -
Java集合框架：代碼使用了
ArrayList來存儲遍歷的結果。ArrayList是Java集合框架中的一個可調整大小的數組實現，用于存儲對象列表。 -
函數參數傳遞：代碼中的
preorder函數接受一個TreeNode類型的參數和一個List<Integer>類型的參數，這展示了如何在Java中傳遞和修改對象引用。 -
基本語法結構：代碼包含了基本的Java語法結構，如類的定義、方法的定義、條件語句（
if）、返回語句（return）和列表的添加操作（result.add）。 -
遞歸的基本條件：在
preorder函數中，遞歸的基本條件是當遇到一個null節點時返回，這避免了遞歸調用的無限循環。 -
方法重載：
Solution類中有兩個名為preorder的方法，但它們的參數列表不同，這是Java方法重載的例子。一個方法是公共的，用于外部調用，另一個方法是私有的，作為輔助方法用于遞歸遍歷。
三、方法二：迭代方法
（一）解題思路
迭代方法通常使用棧來模擬遞歸過程：
- 創建一個空棧，將根節點壓入棧中。
- 當棧不為空時，彈出棧頂元素，訪問該節點，并將其值添加到結果列表中。
- 先將彈出節點的右子節點（如果有）壓入棧中，然后將左子節點（如果有）壓入棧中。這樣可以保證左子節點先被訪問。
- 重復步驟2和3，直到棧為空。
（二）具體代碼
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if (root != null) {stack.push(root);}while (!stack.isEmpty()) {TreeNode node = stack.pop();result.add(node.val); // 訪問節點if (node.right != null) {stack.push(node.right); // 右子節點先入棧}if (node.left != null) {stack.push(node.left); // 左子節點后入棧}}return result;}
}
（三）時間復雜度和空間復雜度
1. 時間復雜度
- 原因：迭代方法訪問樹中每個節點一次。
- 計算：對于具有
N個節點的二叉樹，每個節點都恰好被訪問一次。 - 結果：時間復雜度為
O(N)，其中N是二叉樹中節點的數量。
2. 空間復雜度
- 原因：迭代方法使用棧空間來存儲待訪問的節點，其大小取決于樹的高度。
- 最壞情況：如果樹完全不平衡，每個節點只有左子節點或只有右子節點，棧的深度將達到
N。 - 最好情況：如果樹是完全平衡的，棧的深度將是
logN。 - 結果：空間復雜度介于
O(logN)和O(N)之間，取決于樹的形狀。
3. 總結
- 時間復雜度：
O(N) - 空間復雜度：
O(logN)到O(N)
（四）總結知識點
-
迭代方法：與遞歸方法不同，迭代方法使用棧來模擬遞歸過程，用于遍歷二叉樹的節點。
-
棧數據結構：代碼使用了
Stack類來存儲待訪問的節點。棧是一種后進先出（LIFO）的數據結構，用于在迭代過程中保持節點的訪問順序。 -
二叉樹遍歷：代碼實現了二叉樹的前序遍歷，按照“根-左-右”的順序訪問樹的節點。
-
二叉樹節點定義：代碼中使用了
TreeNode類來定義二叉樹的節點，每個節點包含一個整數值val和兩個指向其左右子節點的指針left和right。 -
Java集合框架：代碼使用了
ArrayList來存儲遍歷的結果。ArrayList是Java集合框架中的一個可調整大小的數組實現，用于存儲對象列表。 -
條件語句：代碼中的
if語句用于檢查當前節點是否有左右子節點，以便將它們添加到棧中。 -
循環結構：
while循環用于在棧不為空的情況下繼續遍歷二叉樹的節點。 -
基本語法結構：代碼包含了基本的Java語法結構，如類的定義、方法的定義、棧的操作（
push和pop）以及列表的添加操作（result.add）。
以上就是解決這個問題的詳細步驟，希望能夠為各位提供啟發和幫助。
