排序算法：
穩(wěn)定性：
穩(wěn)定的排序算法：基數(shù)排序遂赠，冒泡排序久妆，直接插入排序，折半插入排序跷睦，歸并排序筷弦。
不穩(wěn)定的排序算法：快速排序，選擇排序抑诸，希爾排序烂琴，堆排序。
快排：
一次劃分會(huì)將一個(gè)元素pivot放置到最終的位置上哼鬓。
時(shí)間復(fù)雜度：最好O(nlogn)监右，最差O(n^2)，一般為O(nlogn)异希。
空間復(fù)雜度：O(logn)健盒。
穩(wěn)定性：不穩(wěn)定。
void quick_sort(vector<int>& nums, int L, int R){
if (L < R){
int i = L;
int j = R;
int pivot = nums[L];
while (i < j)
{
while (i < j && nums[j] >= pivot){
j--;
}
if (i < j){
nums[i] = nums[j];
i++;
}
while (i < j && nums[i] < pivot){
i++;
}
if (i < j){
nums[j] = nums[i];
j--;
}
}
nums[i] = pivot;
quick_sort(nums, L, i - 1);
quick_sort(nums, i + 1, R);
}
}
遍歷二叉樹：
前序遍歷二叉樹
前序遍歷的遞歸寫法1：
class Solution
{
private:
vector<int> res;
public:
vector<int> preorderTraversal(TreeNode* root){
dfs(root);
return res;
}
void dfs(TreeNode* cur){
if(cur == NULL){
return;
}
//根節(jié)點(diǎn)
res.push_back(cur->val);
//左子節(jié)點(diǎn)
dfs(cur->left);
//右子節(jié)點(diǎn)
dfs(cur->right);
}
};
前序遍歷的遞歸寫法2：
class Solution
{
private:
vector<int> res;
public:
vector<int> preorderTraversal(TreeNode* root){
if(root){
//根節(jié)點(diǎn)
res.push_back(root->val);
//左子節(jié)點(diǎn)
preorderTraversal(root->left);
//右子節(jié)點(diǎn)
preorderTraversal(root->right);
}
return res;
}
};
前序遍歷的迭代寫法1：
vector<int> preorderTraversal(TreeNode* root){
std::vector<int> res;
stack<TreeNode*> stk;
if(root != NULL){
stk.push(root);
}
while(!stk.empty()){
TreeNode* node = stk.top();
if(node != NULL){
stk.pop();
if(node->right){
//添加右子節(jié)點(diǎn)
stk.push(node->right);
}
if(node->left){
//添加左子節(jié)點(diǎn)
stk.push(node->left);
}
//添加中節(jié)點(diǎn)
stk.push(node);
stk.push(NULL);
}
else{
stk.pop();
node = stk.top();
stk.pop();
res.push_back(node->val);
}
}
return res;
}
前序遍歷的迭代寫法2：
vector<int> preoederTraversal(TreeNode* root){
vector<int> res;
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty())
{
TreeNode* node = stk.top();
stk.pop();
if (node != NULL){
//根節(jié)點(diǎn)
res.push_back(node->val);
}
else{
continue;
}
//右子節(jié)點(diǎn)進(jìn)棧
stk.push(node->right);
//左子節(jié)點(diǎn)進(jìn)棧
stk.push(node->left);
}
return res;
}
中序遍歷二叉樹
中序遍歷的遞歸寫法1：
vector<int> res;
vector<int> midorderTraversal(TreeNode* root){
dfs(root);
return res;
}
void dfs(TreeNode* root){
if (root == NULL){
return;
}
dfs(root->left);
res.push_back(root->val);
dfs(root->right);
}
中序遍歷的遞歸寫法2：
vector<int> midorderTraversal(TreeNode* root){
vector<int> res;
if (root){
midorderTraversal(root->left);
res.push_back(root->val);
midorderTraversal(root->right);
}
return res;
}
中序遍歷的迭代寫法1：
vector<int> midorderTraversal(TreeNode* root){
vector<int> res;
stack<TreeNode*> stk;
if (root != NULL){
stk.push(root);
}
while (!stk.empty()){
TreeNode* node = stk.top();
if (node){
stk.pop();
if (node->right){
stk.push(node->right);
}
stk.push(node);
stk.push(NULL);
if (node->left){
stk.push(node->left);
}
}
else{
stk.pop();
node = stk.top();
stk.pop();
res.push_back(node->val);
}
}
return res;
}
中序遍歷的迭代寫法2：
vector<int> midorderTraversal(TreeNode* root){
vector<int> res;
stack<TreeNode*> stk;
TreeNode* cur = root;
while (cur || !stk.empty()){
if (cur){
stk.push(cur);
cur = cur->left;
}
else{
cur = stk.top();
stk.pop();
res.push_back(cur->val);
cur = cur->right;
}
}
return res;
}
后序遍歷二叉樹
后序遍歷的遞歸寫法1：
vector<int> res;
vector<int> postorderTraversal(TreeNode* root){
dfs(root);
return res;
}
void dfs(TreeNode* root){
if (root == NULL){
return;
}
dfs(root->left);
dfs(root->right);
res.push_back(root->val);
}
后序遍歷的遞歸寫法2：
vector<int> postorderTraversal(TreeNode* root){
vector<int> res;
if (root){
postorderTraversal(root->left);
postorderTraversal(root->right);
res.push_back(root->val);
}
return res;
}
后序遍歷的迭代寫法1：
vector<int> postorderTraversal(TreeNode* root){
vector<int> res;
stack<TreeNode*> stk;
if (root != NULL){
stk.push(root);
}
while (!stk.empty()){
TreeNode* node = stk.top();
if (node != NULL){
stk.pop();
stk.push(node);
stk.push(NULL);
if (node->right){
stk.push(node->right);
}
if (node->left){
stk.push(node->left);
}
}
else{
stk.pop();
node = stk.top();
stk.pop();
res.push_back(node->val);
}
}
return res;
}
后序遍歷的迭代寫法2：
vector<int> postorderTraversal(TreeNode* root){
vector<int> res;
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()){
TreeNode* node = stk.top();
stk.pop();
if (node){
res.push_back(node->val);
}
else{
continue;
}
stk.push(node->left);
stk.push(node->right);
}
reverse(res.begin(), res.end());
return res;
}
