二叉树遍历的应用：判断二叉树的类别
昨天的文章讲述了二叉树的先序、中序和后序的遍历方法（递归和非递归）,但是这种遍历方法有什么意义么？今天来讲讲这些算法可以用来做什么，只要稍加更改，我们就可以得到另外一个功能，只需要仅仅几行代码的修改！ 还记得上篇文章二叉树的分类么？今天我们要来说三种树的分类：完全二叉树、平衡二叉树和搜索二叉树！
- 完全二叉树：只有最后一层不需要铺满，其余各层均是满的状态！
- 平衡二叉树：每个节点的左子树和右子树的高度不能超过1，也就是小于等于1
- 搜索二叉树：按照中序遍历必定会得到一个有序的数组，也就是当前节点的值要大于左孩子的值，小于右孩子的值。
我们以下面的二叉树为例，其均符合以上的三个类别！
判断二叉树的类别
是否为平衡二叉树
这里面就存在一个套路，因为判断是否为平衡二叉树的规则对于每个节点都是一致的，也就是说当前节点左子树的高度和其右子树的高度高度差不能超过1，这就很显然可以使用一个递归函数来对每个节点进行遍历，并判断！对于这个递归函数而言，其输入参数应该为当前树的根节点（子树头结点），而返回值为当前树的高度(int)以及是否为平衡树(bool)。对于整棵树而言，只要任意一个子树不为平衡二叉树，那么整个数也不会为平衡二叉树。 由于C++中一个函数不能像Python那样返回多个变量，所以我们将其返回值设计成一个类（很好的思路）！
class ReturnData{
public:
bool isB;
int h;
ReturnData(bool isB, int h){
this->isB = isB;
this->h = h;
}
};
ReturnData* process(TreeNode* head){
if(head == nullptr){
return new ReturnData(true, 0);
}
ReturnData* leftData = process(head->left);
if(!leftData->isB){
return new ReturnData(false, 0);
}
ReturnData* rightData = process(head->right);
if(!rightData->isB){
return new ReturnData(false, 0);
}
if (abs(leftData->h - rightData->h) > 1){
return new ReturnData(false, 0);
}
return new ReturnData(true, max(leftData->h, rightData->h) + 1);
}
bool isB(TreeNode* head){
return process(head)->isB;
}是否为完全二叉树(层次遍历)
由于完全二叉树是主要判断最后一层的节点是否在最左侧以及各层是否填满，我们很容意想到层次遍历的方法，我们使用一个队列来缓冲层次遍历的节点！然后在层次遍历的同时对节点进行判断，规则如下：
- 如果当前节点的右孩子节点不为空，而左孩子节点为空，直接判断false。
- 如果当前节点的左右孩子节点如果有一个为空，我们标记leaf=True，也就是往后遍历的节点的孩子节点必须都为空，否则返回false。
逻辑就是这个样子，我们来看代码：
// 如何判断一棵树为完全二叉树(层次遍历的方法)
bool isCBT(TreeNode* head){
if (head == nullptr){
return true;
}
queue<TreeNode*>* que = new queue<TreeNode*>;
bool leaf = false;
TreeNode* l = nullptr;
TreeNode* r = nullptr;
TreeNode* cur = head;
que->push(cur);
while(!que->empty()){
cur = que->front();
que->pop();
if (leaf && (cur->left != nullptr || cur->right != nullptr) // 如果一个节点右为非空而左为空，那么返回false
|| (cur->right != nullptr && cur->left == nullptr)){ // 如果到达叶节点，那么剩余节点必为叶节点
return false;
}
if (cur->left != nullptr){
que->push(cur->left);
}
if (cur->right != nullptr){
que->push(cur->right);
}
if (cur->left == nullptr || cur->right == nullptr){
leaf = true;
}
}
return true;
}判断是否为搜索二叉树（中序遍历）
搜索二叉树有一个很重要的性质：中序遍历后为一个有序数组，当我们知道这个性质后，我们只需将中序遍历的代码改下就好了，由于我们使用中序遍历可以得到每一个节点，然后当前节点的值和前一个节点的值进行比较，如果大于，那么继续遍历，否则我们返回false！（搜索二叉树不允许重复的数值存在）如果可以成功遍历每个节点，并都满足那个比较条件，那么返回true。 当然这样的话，由于使用了堆栈结构，会有额外的空间复杂度，还有一个Morris算法，可以使用O(1)的空间进行中序遍历，我们以后再说！
// 判断一个二叉树是否为搜索二叉树(中序遍历为一个有序数组) 中序遍历方法
bool isBST_InOrder(TreeNode* head){
if(head == nullptr){
return true;
}
cout << "In Order:" << endl;
stack<TreeNode*>* sta = new stack<TreeNode*>;
TreeNode* cur = head;
int min = INT16_MIN;
while(!sta->empty() || cur != nullptr){
if (cur != nullptr){
sta->push(cur);
cur = cur->left;
}else{
cur = sta->top();
sta->pop();
cout << cur->value << " ";
if ((cur->value - min) > 0){
min = cur->value;
}else{
return false;
}
cur = cur->right;
}
}
cout << endl;
return true;
}