芝士就是菜

红黑树概念 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。 红黑树的性质 每个结点不是红色就是黑色 根节点是黑色的 如果一个节点是红色的，则它的两个孩子结点是黑色的，树中没有连续的红节点 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径中节点个数的两倍？ 极限最短：全黑 极限最长：一黑一红 红黑树结构 123456789101112131415161718192021222324252627282930313233enum Color{ RED, BLACK};template <class K, class V>struct RBTreeNode{ RBTreeNode<K, V&g ...

AVL概念 当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。 一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树： 它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O(log2n)O(log_2 n)O(log2​n)，搜索时间复杂度O(log2nlog_2 nlog2​n) AVL操作 插入 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108bool insert(con ...

606. 根据二叉树创建字符串 我的错误思路 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {& ...

236. 二叉树的最近公共祖先 解法1 规则： 一个是左子树中的节点，一个是右子树中的节点，那么他就是最近的公共祖先 这种做法的时间复杂度是O(H*N)，如果公共祖先在很下面，时间复杂度就比较高 每次找高度次 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354class Solution {public: bool Find(TreeNode* root, TreeNode* x) { if(root==nullptr) return false; /*if(root==x) return true; if(Find(root->left, x)) return true; if(Find(root->right,x)) return true; ...

105. 从前序与中序遍历序列构造二叉树 前序构建树 其中，通过preoder确定根，然后通过inorder分左右子树 比如上边图片的例子，通过preorder知道3为根，查找inorder，找到3所在的位置，分成中序的两个区间，记录左子树节点的个数，将前序序列也分为两个区间，然后递归处理左子树和右子树 我写的 12345678910111213141516171819class Solution {public: TreeNode* buildTree(vector<int> preorder, vector<int> inorder) { if(preorder.size()==0) { return nullptr; } auto mid= find(inorder.begin(),inorder.end(), preorder[0]); int nl=mid-inorder.begin(); TreeN ...

102. 二叉树的层序遍历 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) { ...

二叉搜索树概念 二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树: 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 二叉搜索树实现 结构框架 1234567891011121314151617181920template <class K>struct BSTreeNode{ BSTreeNode *left; BSTreeNode *right; K _key; BSTreeNode(const K &key) : left(nullptr), right(nullptr), _key(key){};};template <class K>class BSTree{ typedef BSTreeNode<K> Node;public:private: Node *_root = nullptr;}; 构造 让编译器提供个默认生成的就可以 ...