- Simple idea: first dfs, record the path, find the corresponding value, and then return; Then compare the two paths (arrays) obtained by dfs and find the last same value from scratch;
- Complexity: time
O
(
n
)
O(n)
O(n) (twice dfs + once traversal), space
O
(
n
)
O(n)
O(n) (recursive call stack + array for path saving)
class Solution {
public:
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
// write code here
vector<int> first,second;
bool isfind=false;
dfs(root, o1, isfind, first);
isfind = false;
dfs(root, o2, isfind, second);
int i=0;
for(;i<first.size()||i<second.size();++i){
if(first[i]!=second[i])break;
}
return first[i-1];
}
void dfs(TreeNode *cur, int val, bool &isfind, vector<int> &path){
if(!cur || isfind) return;
path.push_back(cur->val);
if(cur->val==val) {
isfind=true;
return;
}
if(!isfind) dfs(cur->left, val, isfind, path);
if(!isfind) dfs(cur->right, val, isfind, path);
if(!isfind) path.pop_back();
}
};
- In fact, you can directly dfs, see the next question.
- Direct dfs
- Complexity: time
O
(
n
)
O(n)
O(n) (primary dfs), space
O
(
n
)
O(n)
O(n) (recursive call stack)
- Attention, use! P when judging whether the pointer P is empty, explicitly initialize p to nullptr, otherwise the compiler may perform unpredictable initialization, resulting in judgment errors
class Solution {
public:
int lowestCommonAncestor(TreeNode* root, int p, int q) {
return dfs(root, p, q)->val;
}
TreeNode* dfs(TreeNode *root, int p, int q){
if(!root||root->val==p||root->val==q) return root;
TreeNode *left=nullptr, *right=nullptr; // Note here
// The if judgment in the following two lines is pruned based on the nature of the binary search tree. If the tree is not a binary search tree, you can also directly dfs and remove the if judgment
if(p<root->val||q<root->val) left=dfs(root->left, p, q);
if(p>root->val||q>root->val) right=dfs(root->right, p, q);
if(!left) return right;
if(!right) return left;
return root;
}
};
- One stack is primary and one stack is secondary
When pop is needed, if the auxiliary stack is not empty, pop the auxiliary stack directly; If the auxiliary stack is empty, the elements of the main stack are transferred to the auxiliary stack - Complexity: time
O
(
1
)
O(1)
O(1) (the average complexity of insertion and deletion is), space
O
(
n
)
O(n)
O(n) (two stacks)
- The auxiliary stack is used to record the current minimum value, which is only processed when push ing
If the number pushed in is larger than the auxiliary stack top number, assign it to the stack top element value, and then push; In other cases, push directly - Complexity: time
O
(
1
)
O(1)
O(1) (the complexity of four operations is), space
O
(
n
)
O(n)
O(n) (two stacks)
- Use the auxiliary stack + a pointer to simulate the push in and pop-up operation of the station. If the stack is not empty after traversal or the pointer does not point to the end of the pop-up sequence, it indicates that the push in and pop-up sequence does not correspond.
- Complexity: time
O
(
n
)
O(n)
O(n), space
O
(
n
)
O(n)
O(n) (auxiliary stack)
- Processing with stringstream
- Complexity: time
O
(
n
)
O(n)
O(n), space
O
(
n
)
O(n)
O(n) (two stringstream streams)
class Solution {
public:
string ReverseSentence(string str) {
istringstream iss(str);
ostringstream oss;
stack<string> s;
string tmp;
while(iss>>tmp) s.push(tmp);
while(!s.empty()){
oss<<s.top();
s.pop();
if(!s.empty()) oss<<' ';
}
return oss.str();
}
};
What you learned today
- std::stringstream
- use! P when judging whether the pointer P is empty, explicitly initialize p to nullptr, otherwise the compiler may perform unpredictable initialization, resulting in judgment errors