Last Updated on 2023-01-11 by Clay
Given the root of a binary tree, return the preorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3] Output: [1,2,3]
Example 2:
Input: root = [] Output: []
Example 3:
Input: root = [1] Output: [1]
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
題目給定一顆樹狀結構的資料輸入，我們要做的就是建立一個陣列，將樹狀結構資料的前序遍歷（preorder traversal）儲存在一個數值陣列中。
解題思路
深度優先搜索 DFS
樹狀結構中，前序遍歷其實正好符合深度優先搜索。每次在我們遍歷樹狀資料時，總是優先從左邊的子樹開始遍歷起，遍歷到無法遍歷後再退回上一層開始遍歷右子樹。
DFS 複雜度
| Time Complexity | O(n) |
| Space Complexity | O(1) |
C++ 範例程式碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void dfs(TreeNode* root, vector<int>& v) {
// Base case
if (root == nullptr) {
return;
}
v.emplace_back(root->val);
dfs(root->left, v);
dfs(root->right, v);
}
vector<int> preorderTraversal(TreeNode* root) {
// Init
vector<int> v;
// DFS
dfs(root, v);
return v;
}
};Python 範例程式碼
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
curr = head
length = 0
while curr:
length += 1
curr = curr.next
result = head
for i in range(length//2):
result = result.next
return result堆疊（Stack）
所有的深度優先搜索都可以改寫成堆疊的形式，唯一要注意的是我們要優先儲存左邊節點的值，所以為了符合 FILO（先進後出）的堆疊機制，我們需要先放入左邊節點。
堆疊（Stack） 複雜度
| Time Complexity | O(n) |
| Space Complexity | O(n) |
C++ 範例程式碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
// Init
vector<int> v;
stack<TreeNode*> st({root});
// Stacking
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
if (!node) {
continue;
}
v.emplace_back(node->val);
st.push(node->right);
st.push(node->left);
}
return v;
}
};Python 範例程式碼
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# Init
v = []
st = [root]
# Stacking
while st:
node = st.pop()
if not node:
continue
v.append(node.val)
st.append(node.right)
st.append(node.left)
return v