title: 94. Binary Tree Inorder Traversal
tags:
- backtracking
- stack
categories: leetcode
comments: false
class Solution {
public:
void inorder(TreeNode* root, vector<int>& ret){
if(!root) return;
inorder(root->left, ret);
ret.push_back(root->val);
inorder(root->right, ret);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ret;
inorder(root, ret);
return ret;
}
};option 2 - iterative + stack
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> sta;
TreeNode *p = root;
vector<int> ret;
while (p || !sta.empty()) {
while (p) { // L
sta.push(p);
p=p->left;
}
p = sta.top();
sta.pop();
ret.push_back(p->val); // V
p = p->right; // R
}
return ret;
}
};
- option 1 - dfs
- 時間複雜度：
O(n)，其中 n 是二叉樹的節點數量。每個節點都會被訪問一次。
- 空間複雜度：
O(h)，其中 h 是二叉樹的高度。遞歸的呼叫堆疊的深度取決於樹的高度。
- option 2 - iterative + stack
- 時間複雜度：
O(n)，其中 n 是二叉樹的節點數量。每個節點都會被訪問一次。
- 空間複雜度：
O(h)，其中 h 是二叉樹的高度。堆疊的最大大小取決於樹的高度，最壞情況下為 O(n)（當樹為單鏈時）