仅做一些笔记

数据结构分为数组和链表，数据结构的目的是提升增删改查的效率。算法的本质是基于这两种数据结构进行高效穷举。（1.如何穷举？--递归/dp。2.如何聪明地穷举？--并查集/贪心/KMP）

单链表--双指针

数组--二分搜索/双指针/滑动窗口/前缀+差分

二叉树系列（回溯算法+动态规划）

eg.求二叉树最大深度

1.回溯算法：

class Solution {
public:// 记录最大深度int res = 0;int depth = 0;// 主函数int maxDepth(TreeNode* root) {traverse(root);return res;}// 二叉树遍历框架void traverse(TreeNode* root) {if (root == NULL) {// 到达叶子节点res = max(res, depth);return;}// 前序遍历位置depth++;traverse(root->left);traverse(root->right);// 后序遍历位置depth--;}
};

2.分解问题计算答案

// 定义：输入根节点，返回这棵二叉树的最大深度
int maxDepth(TreeNode* root) {if (root == nullptr) {return 0;}// 递归计算左右子树的最大深度int leftMax = maxDepth(root->left);int rightMax = maxDepth(root->right);// 整棵树的最大深度int res = max(leftMax, rightMax) + 1;return res;
}

eg.二叉树前缀遍历

1.回溯算法：

vector<int> res;// 返回前序遍历结果
vector<int> preorder(TreeNode* root) {traverse(root);return res;
}// 二叉树遍历函数
void traverse(TreeNode* root) {if (root == nullptr) {return;}// 前序遍历位置res.push_back(root->val);traverse(root->left);traverse(root->right);
}

2. 分解问题计算答案

// 定义：输入一棵二叉树的根节点，返回这棵树的前序遍历结果
vector<int> preorder(TreeNode* root) {vector<int> res;if (root == NULL) {return res;}// 前序遍历的结果，root->val 在第一个res.push_back(root->val);// 后面接着左子树的前序遍历结果vector<int> left = preorder(root->left);// 最后接着右子树的前序遍历结果vector<int> right = preorder(root->right);res.insert(res.end(), left.begin(), left.end());res.insert(res.end(), right.begin(), right.end());return res;
}

引用：我的刷题心得：算法的本质 | labuladong 的算法笔记