- 树的递归
- 104. 二叉树的最大深度(简单递归)">104. 二叉树的最大深度(简单递归)
- 110. 平衡二叉树">110. 平衡二叉树
- 450. 删除二叉搜索树中的节点">450. 删除二叉搜索树中的节点
- 437. 路径总和 III">437. 路径总和 III
- 对称二叉树
- 1110. 删点成林(后序遍历&&经常看)">1110. 删点成林(后序遍历&&经常看)
- 226. 翻转二叉树">226. 翻转二叉树
- 617. 合并二叉树">617. 合并二叉树
- 572. 另一棵树的子树">572. 另一棵树的子树
- 404. 左叶子之和（加一个标记）">404. 左叶子之和（加一个标记）
- 513. 找树左下角的值">513. 找树左下角的值
- 层次遍历（广搜）
- 前中后序遍历
- 105. 从前序与中序遍历序列构造二叉树（根据前序和中序返回树）">105. 从前序与中序遍历序列构造二叉树（根据前序和中序返回树）
- 106. 从中序与后序遍历序列构造二叉树">106. 从中序与后序遍历序列构造二叉树
- 144. 二叉树的前序遍历">144. 二叉树的前序遍历
- 94. 二叉树的中序遍历">94. 二叉树的中序遍历
- 145. 二叉树的后序遍历">145. 二叉树的后序遍历
- 538. 把二叉搜索树转换为累加树（中序遍历）">538. 把二叉搜索树转换为累加树（中序遍历）
- 530. 二叉搜索树的最小绝对差(中序遍历)">530. 二叉搜索树的最小绝对差(中序遍历)
- 二叉搜索树
- 99. 恢复二叉搜索树">99. 恢复二叉搜索树
- 669. 修剪二叉搜索树（重点）">669. 修剪二叉搜索树（重点）
- 109. 有序链表转换二叉搜索树（二分法）">109. 有序链表转换二叉搜索树（二分法）
- 897. 递增顺序搜索树（中序遍历）">897. 递增顺序搜索树（中序遍历）
树的递归
104. 二叉树的最大深度(简单递归)
class Solution {public:int maxDepth(TreeNode* root) {if(!root) return 0;return max(maxDepth(root->left), maxDepth(root->right))+1;}};
110. 平衡二叉树
从下往上
class Solution {public:int height(TreeNode* root) {if (root == NULL) {return 0;}int leftHeight = height(root->left);int rightHeight = height(root->right);if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {return -1;} else {return max(leftHeight, rightHeight) + 1;}}bool isBalanced(TreeNode* root) {return height(root) >= 0;//为负数就代表不平衡}};
从上往下
class Solution {public:bool isBalanced(TreeNode* root) {if(!root) return true;if(abs(maxdepth(root->left)-maxdepth(root->right)) > 1) return false;return isBalanced(root->left)&&isBalanced(root->right);}int maxdepth(TreeNode* root) {if(!root) return 0;return max(maxdepth(root->left),maxdepth(root->right))+1;}};
450. 删除二叉搜索树中的节点
根据二叉树的性质
- 如果目标节点大于当前节点值，则去右子树删除
- 如果目标节点小于当前节点值，则去左子树删除
- 如果目标节点就是当前节点，则分为以下三种情况
- 其无左子：右子顶替位置，删除了该节点；
- 其无右子：左子顶替位置，删除了节点
- 其左右都有，左子树转移到右子树的最左节点的左子树上，然后右子树顶替。因为左子树绝对小于根小于右子树。
```cpp
class Solution {
public:
TreeNode deleteNode(TreeNode root, int key)
{
if (root == nullptr) return nullptr;
if (key > root->val) root->right = deleteNode(root->right, key); // 去右子树删除
else if (key < root->val) root->left = deleteNode(root->left, key); // 去左子树删除
else // 当前节点就是要删除的节点
{
} return root;if (! root->left) return root->right; // 情况1，欲删除节点无左子if (! root->right) return root->left; // 情况2，欲删除节点无右子TreeNode* node = root->right; // 情况3，欲删除节点左右子都有while (node->left) // 寻找欲删除节点右子树的最左节点node = node->left;node->left = root->left; // 将欲删除节点的左子树成为其右子树的最左节点的左子树root = root->right; // 欲删除节点的右子顶替其位置，节点被删除
} };
<a name="kv2h7"></a>
### [543. 二叉树的直径](https://leetcode-cn.com/problems/diameter-of-binary-tree/)(就是求任意两个节点的最大路径)
- 经过每个节点的最长的路径就是左边最长加上右边最长。
- 使用一个maxs来存储最长的路径
```cpp
class Solution {
public:
int maxs = 0;
int diameterOfBinaryTree(TreeNode* root) {
depth(root);
return maxs;
}
int depth(TreeNode * node){
if(!node)
return 0;
int l = depth(node->left) , r = depth(node->right);//l和r分别是左右节点的最大深度，最大路径分别是左节点最大深度+右节点最大深度。
maxs = max (l + r, maxs);
return max(l, r) + 1;
}
};
437. 路径总和 III
深度优先搜索
分别计算从每个根节点开始的值
class Solution {
public:
int rootSum(TreeNode* root, int targetSum) {
if (!root) {
return 0;
}
int ret = 0;
if (root->val == targetSum) {
ret++;
}
ret += rootSum(root->left, targetSum - root->val);
ret += rootSum(root->right, targetSum - root->val);
return ret;
}
int pathSum(TreeNode* root, int targetSum) {
if (!root) {
return 0;
}
int ret = rootSum(root, targetSum);//以每一个节点为根节点出发，来寻找targetsum
ret += pathSum(root->left, targetSum);
ret += pathSum(root->right, targetSum);
return ret;
}
};
前缀和
- 为了避免重复计算就，将每一个路径的前缀和通过回溯法的形式来存储在哈希表里面。
- 这里为了避免路径之间的相互影响，使用回溯法。
哈希表的键是前缀和，值是前缀和出现的次数。
class Solution { public: unordered_map<long long,int> hash;//哈希表键是前缀和的值，值为出现的次数。 int ret = 0; void dfs(TreeNode* root, long long sum, int targetSum){ if(!root) return; sum += root->val; if(hash.count(sum-targetSum)) {//每一层都是计算以当前节点为终点的情况的多少。 ret += hash[sum-targetSum]; } hash[sum]++; dfs(root->left, sum, targetSum); dfs(root->right, sum, targetSum); hash[sum]--;//避免干扰到别的分支 return; } int pathSum(TreeNode* root, int targetSum) { hash[0] = 1; dfs(root, 0, targetSum); return ret; } };对称二叉树
递归
class Solution { public: bool isSymmetric(TreeNode* root) { return isSymmetric(root->left, root->right); } bool isSymmetric(TreeNode* left, TreeNode* right) { if(!left&&!right) return true; if(!left||!right||left->val!=right->val) return false; return isSymmetric(left->left,right->right)&&isSymmetric(left->right, right->left); } };迭代
class Solution { public: bool isSymmetric(TreeNode* root) { queue<pair<TreeNode*,TreeNode*>> q; q.emplace(root->left, root->right); while(!q.empty()) { auto node = q.front(); q.pop(); if(!node.first&&!node.second) continue; if(!node.first||!node.second||node.first->val != node.second->val) { return false; } q.emplace(node.first->left, node.second->right); q.emplace(node.first->right, node.second->left); } return true; } };1110. 删点成林(后序遍历&&经常看)
前序遍历不太好写，因为如果将前面的一个节点的子节点置为空，那么，后续的节点不好操作。并且返回值也不好写。由下到上的话删除节点不会影响到上层。
class Solution { public: vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) { vector<TreeNode*> forest; unordered_set<int> dict(to_delete.begin(), to_delete.end());//记住这一种初始化的方法 //哈希表方便查找 root = helper(root , dict, forest); if(root){ forest.push_back(root); } return forest; } TreeNode * helper(TreeNode* root, unordered_set<int> & dict, vector<TreeNode*> &forest){ if(!root) return nullptr; root->left=helper(root->left, dict, forest); root->right=helper(root->right, dict, forest); if(dict.count(root->val)){ if(root->left){ forest.push_back(root->left); } if(root->right){ forest.push_back(root->right); } root = nullptr; } return root; } };226. 翻转二叉树
有点类似对称二叉树的思想
指的注意的是，这里使用left和right来存储root的左右子节点。因为root-left赋值之后，后续的root->right也需要用到root->left。然而此时的root->left已经改变。因此要先保存下来，以免更改。
class Solution { public: TreeNode* invertTree(TreeNode* root) { if(!root) return nullptr; TreeNode* left = root->right, *right = root->left; root->left = invertTree(left); root->right = invertTree(right); return root; } };617. 合并二叉树
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(!root1&&!root2) return nullptr;
if(!root1) return root2;
if(!root2) return root1;
root1->val += root2->val;
root1->left=mergeTrees(root1->left, root2->left);
root1->right=mergeTrees(root1->right, root2->right);
return root1;
}
};
572. 另一棵树的子树
笨比写法，双重dfs
class Solution {
public:
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(!root) return false;
if(root->val == subRoot->val) {
if(dfs(root,subRoot)) {
return true;
}
}
return isSubtree(root->left, subRoot)||isSubtree(root->right, subRoot);
}
bool dfs(TreeNode*root, TreeNode* subRoot) {
if(!root&&!subRoot) return true;
if(!root||!subRoot||root->val!=subRoot->val) return false;
return dfs(root->left, subRoot->left)&&dfs(root->right, subRoot->right);
}
};
树的KMP算法
这个方法需要我们先了解一个小套路：一颗子树上的点在前序遍历中是连续的。可以把两棵树都转换成前序遍历序列，然后使用kmp算法来匹配。
class Solution {
public:
vector <int> sOrder, tOrder;
int maxElement, lNull, rNull;
void getMaxElement(TreeNode *o) {
if (!o) {
return;
}
maxElement = max(maxElement, o->val);
getMaxElement(o->left);
getMaxElement(o->right);
}
void getDfsOrder(TreeNode *o, vector <int> &tar) {
if (!o) {
return;
}
tar.push_back(o->val);
if (o->left) {
getDfsOrder(o->left, tar);
} else {
tar.push_back(lNull);//这里是为空节点填充两个不影响结果的最大值+1的值。
}
if (o->right) {
getDfsOrder(o->right, tar);
} else {
tar.push_back(rNull);
}
}
bool kmp() {//kmp算法
int sLen = sOrder.size(), tLen = tOrder.size();
vector<int> next(tLen, -1);
for(int j = -1, i = 1; i < tLen; i++){//这一次遍历是为了得到next数组，只遍历匹配数组。
while(j!=-1&&tOrder[i]!=sOrder[j+1]) {//千万注意是从-1开始的
j = next[j];
}
if(tOrder[i] == tOrder[j+1]) {//第二个部分为if
j++;
}
next[i] = j;
}
for(int j = -1, i = 0; i < sLen; i++){//这一次遍历是两个数组
while(j!=-1&&sOrder[i]!=tOrder[j+1]) {
j = next[j];//这里之所以是j = next[j]是因为next数组是从pmt数组右移一位左边补0得到的，因此是j = next[j] = pmt[j-1],所以这里是两个j。
}
if(sOrder[i] == tOrder[j+1]){
j++;
}
if(j== tLen-1) {//这里是tlen-1，因为j应该在这个位置。
return true;
}
}
return false;
}
bool isSubtree(TreeNode* s, TreeNode* t) {
maxElement = INT_MIN;
getMaxElement(s);
getMaxElement(t);
lNull = maxElement + 1;
rNull = maxElement + 2;
getDfsOrder(s, sOrder);
getDfsOrder(t, tOrder);
return kmp();
}
};
404. 左叶子之和（加一个标记）
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
return sumOfLeftLeaves(root, false);
}
int sumOfLeftLeaves(TreeNode* root, bool flag){
if(!root->left&&!root->right) {
if(flag) return root->val;
else return 0;
}
int left = root->left? sumOfLeftLeaves(root->left, true):0;
int right = root->right?sumOfLeftLeaves(root->right, false):0;
return left+right;
}
};
513. 找树左下角的值
我的写法（dfs）
比较土，都遍历到了
class Solution {
public:
int res, depth = 0;
int findBottomLeftValue(TreeNode* root) {
dfs(root, 1);
return res;
}
void dfs(TreeNode* root, int depth1) {
if(!root) return;
if(depth1 > depth) {
depth = depth1;
res = root->val;
}
if(root->left) dfs(root->left, depth1+1);
if(root->right) dfs(root->right, depth1+1);
}
};
bfs
更简单速度更快
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
TreeNode* tmp;
q.push(root);
while(!q.empty()) {
tmp = q.front();
q.pop();
if(tmp->right) q.push(tmp->right);
if(tmp->left) q.push(tmp->left);
}
return tmp->val;
}
};
层次遍历（广搜）
637. 二叉树的层平均值（广搜法）
注意for循环的条件不能使用q.size()因为q.size()是在不停的变化的。
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
double ave = 0;
vector<double> res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
int n = q.size();
for(int i = 0; i < n; i++) {//这里使用q.size()是会变得，所以使用n
auto node = q.front();
q.pop();
ave = ave*i/(i+1) + (double)node->val/(i+1);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
res.push_back(ave);
ave = 0;
}
return res;
}
};
429. N 叉树的层序遍历
bfs
和上题类似，只是二叉树换成了n叉树
class Solution { public: vector<vector<int>> levelOrder(Node* root) { if(!root) return {}; queue<Node*> q; vector<vector<int>> res; vector<int> vec; q.push(root); while(!q.empty()) { int n = q.size(); vec.clear(); for(int i = 0; i < n; i++){ Node* node = q.front(); q.pop(); vec.push_back(node->val); for(int j = 0; j < node->children.size(); j++){ if(node->children[j]) q.push(node->children[j]); } } res.push_back(vec); } return res; } };dfs
class Solution { public: vector<vector<int>> levelOrder(Node* root) { vector<vector<int>> ans; auto dfs = [&ans] (auto& dfs, int level, Node* node) { if (!node) { return; } if (ans.size() == level) { ans.push_back({}); } ans[level].push_back(node->val); ++level; for(auto n: node->children) { dfs(dfs, level, n); } }; dfs(dfs, 0, root); return ans; } };653. 两数之和 IV - 输入 BST
哈希表
class Solution { public: unordered_set<int> se; bool findTarget(TreeNode* root, int k) { if(!root) return false; int val = root->val; if(se.find(k-val) != se.end()) return true; se.insert(root->val); return findTarget(root->left,k)||findTarget(root->right, k); } };双指针二分法
class Solution { public: vector<int> vec; void inorderTraversal(TreeNode *node) { if (node == nullptr) { return; } inorderTraversal(node->left); vec.push_back(node->val); inorderTraversal(node->right); } bool findTarget(TreeNode *root, int k) { inorderTraversal(root); int left = 0, right = vec.size() - 1; while (left < right) { if (vec[left] + vec[right] == k) { return true; } if (vec[left] + vec[right] < k) { left++; } else { right--; } } return false; } };235. 二叉搜索树的最近公共祖先
笨比写法
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { queue<TreeNode*> que; int a = q->val, b = p->val; if(a > b) { swap(a, b); } que.push(root); while(!que.empty()) { TreeNode* node = que.front(); que.pop(); if(node->val >= a&&node->val <= b) return node; if(node->left) que.push(node->left); if(node->right) que.push(node->right); } return NULL; } };正确答案
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { TreeNode* ancestor = root; while (true) { if (p->val < ancestor->val && q->val < ancestor->val) { ancestor = ancestor->left; } else if (p->val > ancestor->val && q->val > ancestor->val) { ancestor = ancestor->right; } else { break; } } return ancestor; } };236. 二叉树的最近公共祖先
这一题与上一题不同的地方在于，这一题不是二叉搜索树
这一题的想法比较特殊，需要考虑右边和左边的情况，对于递归中的某一个节点来说当一个节点的l与r都不为空时，就代表这个节点就是 答案
- 当一个节点的l与r有一个为空时，就证明答案位于另一子树或者祖先中。
- 当一个节点的l与r都为空时，就代表上层l为空。
返回值就是当前节点是否含有目标节点。
思路非常黑科技，建议反复研究。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL || p == root || q == root) {
return root;
}
TreeNode* l = lowestCommonAncestor(root->left, p, q);
TreeNode* r = lowestCommonAncestor(root->right, p, q);
if(!l&&!r) {
return NULL;
} else if(l&&r) {
return root;
} else {
if(!r) return l;
else return r;
}
}
};
前中后序遍历
105. 从前序与中序遍历序列构造二叉树（根据前序和中序返回树）
- 根据前序是父左右，中序是左父右。可以知道根节点在前序的第一个值
- 又根据中序的特点，可以知道左子树的节点个数。根据左子树的个数来得到前序中子数的位置。
```cpp
class Solution {
private:
unordered_map
public:
TreeNode* myBuildTree(const vector
// 前序遍历中的第一个节点就是根节点
int preorder_root = preorder_left;
// 在中序遍历中定位根节点
int inorder_root = index[preorder[preorder_root]];
// 先把根节点建立出来
TreeNode* root = new TreeNode(preorder[preorder_root]);
// 得到左子树中的节点数目
int size_left_subtree = inorder_root - inorder_left;
// 递归地构造左子树，并连接到根节点
// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);//此处都减去了根节点
// 递归地构造右子树，并连接到根节点
// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);//这里代表的意思是区间。
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
// 构造哈希映射，帮助我们快速定位根节点
for (int i = 0; i < n; ++i) {
index[inorder[i]] = i;
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
};
<a name="zhSbw"></a>
### [889. 根据前序和后序遍历构造二叉树](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/)（与上题类似）
- 需要找到左子树与右子树
- 最好还是加上所有边界条件
```cpp
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder, int preleft, int preright, int posleft, int posright) {
if(preleft>preright) {
return nullptr;
}
if(preleft == preright) {
TreeNode* root = new TreeNode(preorder[preleft]);
return root;
}
TreeNode* root = new TreeNode(preorder[preleft]);
int left = hash[preorder[preleft+1]];
int leftsize = left - posleft + 1;
root->left = constructFromPrePost(preorder, postorder, preleft+1, preleft+leftsize, posleft, left);
root->right = constructFromPrePost(preorder, postorder,preleft+leftsize+1, preright, left+1,posright-1);
return root;
}
};
106. 从中序与后序遍历序列构造二叉树
class Solution {
int post_idx;
unordered_map<int, int> idx_map;
public:
TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){
// 如果这里没有节点构造二叉树了，就结束
if (in_left > in_right) {
return nullptr;
}
// 选择 post_idx 位置的元素作为当前子树根节点
int root_val = postorder[post_idx];
TreeNode* root = new TreeNode(root_val);
// 根据 root 所在位置分成左右两棵子树
int index = idx_map[root_val];
// 下标减一
post_idx--;
// 构造右子树
root->right = helper(index + 1, in_right, inorder, postorder);
// 构造左子树
root->left = helper(in_left, index - 1, inorder, postorder);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// 从后序遍历的最后一个元素开始
post_idx = (int)postorder.size() - 1;
// 建立（元素，下标）键值对的哈希表
int idx = 0;
for (auto& val : inorder) {
idx_map[val] = idx++;
}
return helper(0, (int)inorder.size() - 1, inorder, postorder);
}
};
144. 二叉树的前序遍历
- 这题使用递归的方法来写很简单
-
递归
class Solution { public: vector<int> res; vector<int> preorderTraversal(TreeNode* root) { dfs(root); return res; } void dfs(TreeNode* root) { if(!root) return; res.push_back(root->val); dfs(root->left); dfs(root->right); } };迭代(先记下来吧)
迭代需要借助栈来写，先靠最左边的路径来，然后根据栈的后进先出的原则在来计算右节点
前序遍历的顺序是 前左右思路：比如实例中 我们先把根节点放进去栈中 按顺序我们的根节点是要在最前面的 所以把根节点弹出 用一个结点来存储弹出的结点 并把弹出的结点存进数组中 然后再把弹出的结点 的右孩子和左孩子入栈 注意顺序 先把右孩子入栈再把左孩子入栈 因为栈的特点是先入后出 你先把右孩子入栈 再入左孩子 那么右孩子就是最后一个弹出的 这样才符合前序序列class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int>res; if(root==NULL){ return res; } stack<TreeNode*>stk; TreeNode*node=root; stk.push(node); while(!stk.empty()) { node=stk.top(); stk.pop(); if(node==NULL) continue; res.push_back(node->val); stk.push(node->right); stk.push(node->left); } return res; } };94. 二叉树的中序遍历
递归的很简单，这里只贴出迭代的写法
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> stk; while (root != nullptr || !stk.empty()) { while (root != nullptr) { stk.push(root); root = root->left; } root = stk.top(); stk.pop(); res.push_back(root->val); root = root->right; } return res; } };145. 二叉树的后序遍历
反转父右左
这里可以根据前序遍历来写。
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int>res; if(root==NULL){ return res; } stack<TreeNode*>stk; TreeNode*node=root; stk.push(node); while(!stk.empty()) { node=stk.top(); stk.pop(); if(node==NULL) continue; res.push_back(node->val); stk.push(node->left); stk.push(node->right); } reverse(res.begin(), res.end()); return res; } };正常迭代
和中序遍历的迭代写法非常相似。但是后序遍历需要先考虑右节点是否遍历到。
- 中序遍历中可以直接访问该节点，因为左子树访问完了。而后续遍历，只能确定左子树访问完了，无法确定右子树是否访问过。
- 因此需要一个历史节点pre来记载右子树是否访问过。这里的pre就是上一次访问的节点。如果右节点上一次没有访问过，就需要将root改为右节点。
如果根节点需要不停更换就需要使用while(!root||stk.empty())
class Solution { public: vector<int> postorderTraversal(TreeNode *root) { vector<int> res; if (root == nullptr) { return res; } stack<TreeNode *> stk; TreeNode *prev = nullptr; while (root != nullptr || !stk.empty()) { while (root != nullptr) { stk.emplace(root); root = root->left; } root = stk.top(); stk.pop(); if (root->right == nullptr || root->right == prev) {//如果此时的root没有右节点，或者右节点已经输出过。就可以直接 //输出当前的值 res.emplace_back(root->val); prev = root; root = nullptr;//意思就是不能在输入栈中了，在此种情况。也强迫从栈中选择。 } else {//当前的root存在右节点，且右节点没有输出，则把当前的root收回去。 stk.emplace(root); root = root->right; } } return res; } };538. 把二叉搜索树转换为累加树（中序遍历）
前缀和写法（笨比写法）
前缀和加上反中序遍历
class Solution { public: vector<int> vec; int index = 0; TreeNode* convertBST(TreeNode* root) { getvec(root); partial_sum(vec.begin(), vec.end(), vec.begin()); setBST(root); return root; } void getvec(TreeNode* root) { if(!root) return; getvec(root->right); vec.push_back(root->val); getvec(root->left); } void setBST(TreeNode* root) { if(!root) return; setBST(root->right); root->val = vec[index++]; setBST(root->left); } };反中序遍历（正确答案）
就是之前的简化版本，没必要使用前缀和。
class Solution { public: int sum = 0; TreeNode* convertBST(TreeNode* root) { if (root != nullptr) { convertBST(root->right); sum += root->val; root->val = sum; convertBST(root->left); } return root; } };530. 二叉搜索树的最小绝对差(中序遍历)
二叉搜索树就要记得使用中序遍历！！！！！
千万注意什么时候需要使用引用参数。
class Solution { public: int minDiffInBST(TreeNode* root) { int ans = INT_MAX, pre = -1; dfs(root, pre, ans); return ans; } void dfs(TreeNode* root, int& pre, int &ans){//这里必须使用引用，因为后一层的pre需要改变前一层的pre的值!!!!。 if(!root) return; dfs(root->left, pre, ans);//因为这个里面改变的pre不会影响到上一层，如果不使用引用，那么每一层的pre都是独立的。 if(pre == -1) { pre = root->val; } else { ans = min(ans, abs(root->val-pre)); pre = root->val; } dfs(root->right, pre, ans); } };二叉搜索树
99. 恢复二叉搜索树
用O(n)来写
高级写法有点小复杂，不想弄了
class Solution { private: priority_queue<int, vector<int> , greater<int>> q; public: void recoverTree(TreeNode* root) { dfs(root); helper(root); } void dfs(TreeNode* root) { if(!root) return; dfs(root->left); cout << root->val << endl; q.push(root->val); dfs(root->right); } void helper(TreeNode* root) { if(!root) return; helper(root->left); root->val = q.top(); q.pop(); helper(root->right); } };Morris中序遍历
class Solution { public: void recoverTree(TreeNode* root) { TreeNode *x = nullptr, *y = nullptr, *pred = nullptr, *predecessor = nullptr; while (root != nullptr) { if (root->left != nullptr) { // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止 predecessor = root->left; while (predecessor->right != nullptr && predecessor->right != root) { predecessor = predecessor->right; } // 让 predecessor 的右指针指向 root，继续遍历左子树 if (predecessor->right == nullptr) { predecessor->right = root; root = root->left; } // 说明左子树已经访问完了，我们需要断开链接 else { if (pred != nullptr && root->val < pred->val) { y = root; if (x == nullptr) { x = pred; } } pred = root; predecessor->right = nullptr; root = root->right; } } // 如果没有左孩子，则直接访问右孩子 else { if (pred != nullptr && root->val < pred->val) { y = root; if (x == nullptr) { x = pred; } } pred = root; root = root->right; } } swap(x->val, y->val); } };669. 修剪二叉搜索树（重点）
多理解一下递归的想法，总是写不出来
根据二叉搜索树的特点，一剪就是一整个树枝
class Solution { public: TreeNode* trimBST(TreeNode* root, int low, int high) { if(!root) return nullptr; if(root->val > high) return trimBST(root->left, low, high); if(root->val < low) return trimBST(root->right, low, high); root->left = trimBST(root->left, low, high); root->right = trimBST(root->right, low, high); return root; } };109. 有序链表转换二叉搜索树（二分法）
左闭右开
二分法的思想，这里注意使用的是左闭右开。
class Solution { public: TreeNode* sortedListToBST(ListNode* head) { vector<int> list; while(head) { list.push_back(head->val); head = head->next; } return buildtree(list, 0, list.size()); } TreeNode* buildtree(vector<int> & list, int l , int r) { if(l >= r) return nullptr; int mid = l + (r-l)/2; TreeNode* node = new TreeNode(list[mid]); node->left = buildtree(list, l, mid); node->right = buildtree(list, mid+1, r); return node; } };左闭右闭
class Solution { public: TreeNode* sortedListToBST(ListNode* head) { vector<int> list; while(head) { list.push_back(head->val); head = head->next; } return buildtree(list, 0, list.size()-1); } TreeNode* buildtree(vector<int> & list, int l , int r) { if(l > r) return nullptr; int mid = l + (r-l)/2; TreeNode* node = new TreeNode(list[mid]); node->left = buildtree(list, l, mid-1); node->right = buildtree(list, mid+1, r); return node; } };897. 递增顺序搜索树（中序遍历）
简单方法就是使用一个数组来存储，但是太不优雅
- 注意使用一个成员变量来代表节点，可以很方便的维护一个pre节点 ```cpp class Solution { private: TreeNode *resNode;
public: void inorder(TreeNode *node) { if (node == nullptr) { return; } inorder(node->left);
// 在中序遍历的过程中修改节点指向
resNode->right = node;
node->left = nullptr;
resNode = node;
inorder(node->right);
}
TreeNode *increasingBST(TreeNode *root) {
TreeNode *dummyNode = new TreeNode(-1);
resNode = dummyNode;
inorder(root);
return dummyNode->right;
}
};
<a name="Bbrvv"></a>
## 字典树
<a name="Pnlpl"></a>
### [208. 实现 Trie (前缀树)](https://leetcode-cn.com/problems/implement-trie-prefix-tree/)
- 类似有26个叉的树，对应26个英文字母。
```cpp
class Trie {
private:
vector<Trie*> next;
bool isend;
public:
Trie() : isend(false),next(26){
}//构造函数
Trie* presearch(string prefix) {
Trie* node = this;//这里的this相当于根节点，因为是实例的节点。
for(auto it : prefix) {
if(node->next[it-'a'] == nullptr) {
return nullptr;
}
node = node->next[it-'a'];
}
return node;
}//前缀搜索
void insert(string word) {
Trie *node = this;
for(auto it : word) {
if(!node->next[it-'a']) {
node->next[it-'a'] = new Trie;
}
node = node->next[it-'a'];
}
node->isend = true;
}//插入
bool search(string word) {
return presearch(word)&&presearch(word)->isend;
}//搜索到前缀，并且是结尾。
bool startsWith(string prefix) {
return presearch(prefix);
}//直接返回前缀搜索结果即可
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
若有收获，就点个赞吧
0 人点赞
