一、完全二叉树
1、什么是完全二叉树
完全二叉树是这样定义的：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）
上面的定义看起来比较复杂。事实上，完全二叉树的节点满足如下规律：
所有节点只存在3种情况：1、有左右2个孩子；2、只有左孩子；3、没有孩子（叶节点），即不存在只有右孩子的情况；我们采用层序遍历的方式遍历节点，当遍历到某一个节点，它只有左孩子，或者没有孩子，则后序所有节点一定都是叶节点。如下所示是完全二叉树
2、怎么判断是否是完全二叉树
根据上述规律，我们可以设计算法：采用层序（广度优先）方法遍历节点，每一个节点都要满足上诉条件1。当遍历到某个节点不是有左右孩子时，开始检测后面节点是否全部是叶节点，如果满足，则是完全二叉树。
至于怎么写层序遍历，可以参考下面文章二叉树的宽度（广度）优先遍历C++_二叉树广度优先遍历c语言-CSDN博客
代码如下
bool IsCST(TreeNode* root){ bool flag = false; //一个flag，记录已经遍历到不是左右孩子双全的节点 if (root == nullptr) { return true; } std::queue<TreeNode*> node_que; node_que.push(root); while(!node_que.empty()) { // 弹出队首节点 TreeNode* node = node_que.front(); node_que.pop(); // flag为true if(flag) { // 条件二：flag是true，存在任何孩子都不是完全二叉树 if(node->left || node->right) return false; } else { if (node->left) { // 左孩子入队 node_que.push(node->left); //条件二：有左孩子没有右孩子，则flag置true if (!node->right) { flag = true; } else { // 右孩子入队 node_que.push(node->right); } } else { // 条件一：无左孩子但有右孩子，不是完全二叉树 if(node->right) return false; // 条件二：无左孩子无右孩子，则flag同样置true flag = true; } } } return true;}二、搜索二叉树
1、什么是搜索二叉树
一个二叉搜索树要满足如下条件：
节点的左子树只包含 小于 当前节点的数节点的右子树只包含 大于 当前节点的数所有左子树和右子树自身必须也是二叉搜索树。空树也是二叉搜索树。
例如下面是一个二叉搜索树：
2、怎么判断是否是搜索二叉树
二叉搜索树要求任意节点的左子树都要比该节点小，而右子树比该节点大。那么，我们如果采用中序遍历的方式遍历一个二叉搜索树，理应得到一个严格递增的数列。所以我们可以考虑结合中序遍历的算法实现对搜索二叉树的判断。
我们改变一下中序遍历的代码，就可以得到如下算法。
int s_val = 0; // 记录上一个节点的值bool b_first = true; //记录是不是中序第一个节点bool IsBST(TreeNode *root) {// 根节点为空，直接返回if (nullptr == root) {return true;}// 1）判断左子树是不是搜索二叉树if (!IsBST(root->left)) {return false;}// 比较当前值与左子树最后一个值if (!b_first && root->val < s_val) {return false;}else {s_val = root->val;b_first = false;}// 3）判断右子树是不是搜索二叉树return IsBST(root->right);}三、平衡二叉树
1、什么是平衡二叉树
一棵平衡二叉树必须要满足如下条件：
每个节点左右两个子树的高度差不超过1每个左子树和右子树自身必须也是平衡二叉树空树也是平衡二叉树。
例如下图就是一棵平衡二叉树
2、怎么判断是否是平衡二叉树
根据平衡二叉树的性质，我们只要判断左右子树分别是平衡二叉树，并且左右子树的高度差在1以内即可。
我们很自然的想到用递归法求解。在递归中我们需要提取2个信息：一是子树是否是平衡的；二是子树的高度，方便返回判断是否和兄弟子树的高度相差在1以内。
代码如下
struct Result{ int height; //树的高度 bool is_balance; //是否平衡 Result(int l=0, bool is_b=true):height(l), is_balance(is_b){}};Result IsBalanceTree(TreeNode* root){ if (root == nullptr) { return Result(); } Result ret_left = IsBalanceTree(root->left); Result ret_right = IsBalanceTree(root->right); int lev = std::max(ret_left.height, ret_right.height) + 1; int lv_diff = std::abs(ret_left.height - ret_right.height); if (!ret_left.is_balance || !ret_right.is_balance || lv_diff > 1) { return Result(lev, false); } return Result(lev, true);}四、满二叉树
1、什么是满二叉树
如果一棵树除最后一层无任何子节点外，每一层上的所有节点都有两个子节点，则这棵树是满二叉树。
2、怎么判断是否是满二叉树
假设根节点所在是1层，则一棵满二叉树的每k层共有2^(k-1)个节点，一棵满二叉树的总结点个数为(2^k) -1。根据这个数学特征，我们采用层序遍历的方法可以很方便地判断是否是满二叉树。
代码如下
bool IsFullTree(TreeNode* root){ if (root == nullptr) return true; std::queue<TreeNode*> node_que; std::unordered_map<TreeNode*, int> node_lv; //记录每个节点所在层数 int cur_lv = 1; //记录当前遍历到的层数 int node_count = 0; // 当前层节点计数 node_que.push(root); node_lv[root] = 1; while(!node_que.empty()) { // 弹出队首节点 TreeNode* node = node_que.front(); node_que.pop(); //换层 if (node_lv[node] != cur_lv) { // 计算上一层是否满足条件，不满足数学条件，则返回false if(node_count != pow(2, cur_lv-1)) return false; // 重置此层节点计数 node_count = 0; cur_lv = node_lv[node]; } node_count++; // 左孩子进队列 if (node->left) { node_que.push(node->left); node_lv[node->left] = cur_lv + 1; } // 右孩子进队列 if (node->right) { node_que.push(node->right); node_lv[node->right] = cur_lv + 1; } } //检测最后一层是否满足节点个数条件 if(node_count != pow(2, cur_lv-1)) return false; return true;}