满二叉树、完全二叉树、二叉搜索树

满二叉树：只有度为0或2的结点，并且度为0的结点在同一层上
完全二叉树：除了最底层结点可能没填满，其他各层都填满了，并且最底层的结点都集中在最左边。
以上是没数值的树
二叉搜索树：是有数值的树，而且保持有序

二叉树的存储方式

链式存储、顺序存储（数组）
顺序存储：对于下标为i的节点，左孩子是i2+1，右孩子是i2+2
链式存储：

  1. struct TreeNode {
  2.     int val;
  3.     TreeNode *left;
  4.     TreeNode *right;
  5.     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  6. };

二叉树的遍历、插入、反转

  1. class Solution {
  2. public:
  3.     void dfs(TreeNode *p) {
  4.         if(p->left) dfs(p->left);
  5.         cout<<p->val<<' ';
  6.         if(p->right) dfs(p->right);
  7.     }
  8.     TreeNode* add(TreeNode *p, int value) {
  9.         if(p == nullptr) {
  10.             return new TreeNode(value);
  11.         }else if(p->val > value) {
  12.             p->left = add(p->left, value);
  13.             return p;
  14.         }else if(p->val < value) {
  15.             p->right = add(p->right, value);
  16.             return p;
  17.         }
  18.     }
  19.     TreeNode* invertTree(TreeNode* root) {
  20.         if(root == nullptr) return root;
  21.         swap(root->left, root->right);
  22.         root->left = invertTree(root->left);
  23.         root->right = invertTree(root->right);
  24.         return root;
  25.     }
  26. };

二叉树的顺序存储

  1.     // 二叉树的数组初始化
  2.     TreeNode* init(vector<int> v) {
  3.         if(v.size()==0) return nullptr;
  4.         TreeNode* root = new TreeNode(v[0]);
  5.         queue<TreeNode*> q;
  6.         q.push(root);
  7.         for(int i=1;i<v.size();i++) {
  8.             TreeNode* tmp = q.front();q.pop();
  9.             if(v[i]!=-1) {
  10.                 tmp->left = new TreeNode(v[i]);
  11.                 q.push(tmp->left);
  12.             }
  13.             if(v[++i]!=-1) {
  14.                 tmp->right = new TreeNode(v[i]);
  15.                 q.push(tmp->right);
  16.             }
  17.         }
  18.         return root;
  19.     }

完全二叉树深度的利用

https://leetcode-cn.com/problems/count-complete-tree-nodes/
log*log时间复杂度计算完全二叉树节点个数

  1.     pair<int,int> countDepth(TreeNode* p) {
  2.         int l=0, r=0;
  3.         while(p) {
  4.             l++;
  5.             p=p->left;
  6.         }
  7.         while(p) {
  8.             r++;
  9.             p=p->right;
  10.         }
  11.         return make_pair(l,r);
  12.     }
  13.     int countNodes(TreeNode* root) {
  14.         if(root==nullptr) return 0;
  15.         int res = 1;
  16.         auto left = countDepth(root->left);
  17.         if(left.first == left.second) {
  18.             res+=(1<<left.first)-1;
  19.         }else {
  20.             res+=countNodes(root->left);
  21.         }
  22.         auto right = countDepth(root->right);
  23.         if(right.first == right.second) {
  24.             res+=(1<<right.first)-1;
  25.         }else {
  26.             res+=countNodes(root->right);
  27.         }
  28.         return res;
  29.     }

平衡二叉树

二叉树每个节点左右子树高度差不超过1

最近公共祖先

方法一：求LCA(x,y)只需要从x向上遍历到根节点并且把每个节点标记，然后从y向上遍历知道需要标记过的节点
方法二：fx代表x节点的后代中是否有x或y，那么lca就是满足左右子树都包含x或y，或者本身是x或y且左子树或右子树包含x或y
方法三：如果是有序二叉树，还可以利用节点在区间内来判断节点是否在子树内