class Solution { public: int searchInsert(vector<int>& nums, int target) { int n = nums.size(); int left = 0; int right = n; // 我们定义target在左闭右开的区间里，[left, right) while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间 int middle = left + ((right - left) >> 1); if (nums[middle] > target) { right = middle; // target 在左区间，因为是左闭右开的区间，nums[middle]一定不是我们的目标值，所以right = middle，在[left, middle)中继续寻找目标值 } else if (nums[middle] < target) { left = middle + 1; // target 在右区间，在 [middle+1, right)中 } else { // nums[middle] == target return middle; // 数组中找到目标值的情况，直接返回下标 } } return right; } }; 

void kmp(int* next, const string& s){ next[0] = -1; int j = -1; for(int i = 1; i < s.size(); i++){ while (j >= 0 && s[i] != s[j + 1]) { j = next[j]; } if (s[i] == s[j + 1]) { j++; } next[i] = j; } } 

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; 

void traversal(TreeNode* cur, vector<int>& vec) { if (cur == NULL) return; vec.push_back(cur->val); // 中 ，同时也是处理节点逻辑的地方 traversal(cur->left, vec); // 左 traversal(cur->right, vec); // 右 } 

void traversal(TreeNode* cur, vector<int>& vec) { if (cur == NULL) return; traversal(cur->left, vec); // 左 vec.push_back(cur->val); // 中 ，同时也是处理节点逻辑的地方 traversal(cur->right, vec); // 右 } 

void traversal(TreeNode* cur, vector<int>& vec) { if (cur == NULL) return; vec.push_back(cur->val); // 中 ，同时也是处理节点逻辑的地方 traversal(cur->left, vec); // 左 traversal(cur->right, vec); // 右 } 

vector<int> preorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; if (root != NULL) st.push(root); while (!st.empty()) { TreeNode* node = st.top(); if (node != NULL) { st.pop(); if (node->right) st.push(node->right); // 右 if (node->left) st.push(node->left); // 左 st.push(node); // 中 st.push(NULL); } else { st.pop(); node = st.top(); st.pop(); result.push_back(node->val); // 节点处理逻辑 } } return result; } 

vector<int> inorderTraversal(TreeNode* root) { vector<int> result; // 存放中序遍历的元素 stack<TreeNode*> st; if (root != NULL) st.push(root); while (!st.empty()) { TreeNode* node = st.top(); if (node != NULL) { st.pop(); if (node->right) st.push(node->right); // 右 st.push(node); // 中 st.push(NULL); if (node->left) st.push(node->left); // 左 } else { st.pop(); node = st.top(); st.pop(); result.push_back(node->val); // 节点处理逻辑 } } return result; } 

vector<int> postorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; if (root != NULL) st.push(root); while (!st.empty()) { TreeNode* node = st.top(); if (node != NULL) { st.pop(); st.push(node); // 中 st.push(NULL); if (node->right) st.push(node->right); // 右 if (node->left) st.push(node->left); // 左 } else { st.pop(); node = st.top(); st.pop(); result.push_back(node->val); // 节点处理逻辑 } } return result; } 

vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> que; if (root != NULL) que.push(root); vector<vector<int>> result; while (!que.empty()) { int size = que.size(); vector<int> vec; for (int i = 0; i < size; i++) {// 这里一定要使用固定大小size，不要使用que.size() TreeNode* node = que.front(); que.pop(); vec.push_back(node->val); // 节点处理的逻辑 if (node->left) que.push(node->left); if (node->right) que.push(node->right); } result.push_back(vec); } return result; } 

int getDepth(TreeNode* node) { if (node == NULL) return 0; return 1 + max(getDepth(node->left), getDepth(node->right)); } 

int countNodes(TreeNode* root) { if (root == NULL) return 0; return 1 + countNodes(root->left) + countNodes(root->right); } 

backtracking() { if (终止条件) { 存放结果; } for (选择：选择列表（可以想成树中节点孩子的数量）) { 递归，处理节点; backtracking(); 回溯，撤销处理结果 } }