请参阅注释30-确定是否平衡二叉树（AVL），二叉搜索树（BST），完整二叉树和

条件: 对于当前节点

写这些条件，您可以得到一个递归函数，使用-1来识别树的不平衡，如果平衡，它将返回精确的高度

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <math.h>
using namespace std;
struct TreeNode {
    int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
	int process(TreeNode *head) {
		if (head == NULL)
			return 0;
		int h1 = process(head->left);
		if (h1 == -1)
			return -1;
		int h2 = process(head->right);
		if (h2 == -1)
			return -1;
		if (abs(h1 - h2) > 1)
			return -1;
		return max(h1, h2) + 1;
	}
	bool isBalanced(TreeNode* root) {
		if (root == NULL)
			return true;
		
		int res = process(root);
		if (res == -1) {
			cout << "此树不平衡!\n";
			return false;
		}
		cout << "此树平衡，树高为：" << res;
		return true;
	}
};
int main(int argc, char* argv[]){
	TreeNode *head = new TreeNode(1);
	head->left = new TreeNode(2);
	//head->right = new TreeNode(3);
	//head->left->right = new TreeNode(5);
	head->left->left = new TreeNode(6);
	Solution s;
	s.isBalanced(head);
	return 0;
}

将非递归有序遍历的打印时间更改为前一个数字，以确定它是否大于前一个数字.

需要使用变量pre保存前一个数字判断二叉排序树，如果它看起来小于前一个数字，则返回false

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <math.h>
#include <climits>
using namespace std;
struct TreeNode {
    int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
	bool isValidBST(TreeNode* root) {
		if (root != NULL) {
			stack<TreeNode*> stk;
			long pre = LONG_MIN;
			while (!stk.empty() || root != NULL) {
				if (root != NULL) {
					stk.push(root);
					root = root->left;
				} else {
					root = stk.top();
					stk.pop();
					if (root->val > pre) {
						pre = root->val;
					} else {
						return false;	// 中序遍历应当是升序的
					}
					root = root->right;
				}
			}
			return true;
		}
		return true;	// 空树是BST
	}
};
int main(int argc, char* argv[]){
	TreeNode *head = new TreeNode(2);
	head->left = new TreeNode(1);
	head->right = new TreeNode(3);
	head->right->right = new TreeNode(6);
	Solution s;
	if (s.isValidBST(head))
		cout << "是二叉搜索树！\n";
	else
		cout << "不是二叉搜索树！\n";
	return 0;
}

二叉树从上到下，从左到右遍历

条件如下:

如果节点在遍历期间有一个右子节点而没有左子节点，则它一定不能是一个完整的二叉树遍历过程. 如果一个节点有左子节点，没有右子节点，也没有两个子节点，则开始一个阶段并继续. 在遍历后的节点之后出现的节点必须是叶节点，否则不能是完整的二叉树. 如果遍历的末尾没有违反1和2，则该树是完整的二叉树

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <math.h>
#include <climits>
using namespace std;
struct TreeNode {
    int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
	bool isCBT(TreeNode* root) {
		if (root != NULL) {
			bool leaf = false;
			queue<TreeNode*> Q;
			Q.push(root);
			while (!Q.empty()) {
				TreeNode *tmp = Q.front();
				Q.pop();
				TreeNode *lchild = tmp->left;
				TreeNode *rchild = tmp->right;
				if ((leaf && (lchild != NULL || rchild != NULL)) || 
					lchild == NULL && rchild != NULL) {
					return false;
				}
				if (lchild != NULL) {
					Q.push(lchild);
				}
				if (rchild != NULL) {
					Q.push(rchild);
				}
				if ((lchild != NULL && rchild == NULL) ||
					(lchild == NULL && rchild == NULL)) {
					leaf = true;
				}
			}
		}
		return true;	// 空树是CBT
	}
};
int main(int argc, char* argv[]){
	TreeNode *head = new TreeNode(2);
	head->left = new TreeNode(1);
	head->right = new TreeNode(3);
	head->right->right = new TreeNode(6);
	head->left->left = new TreeNode(5);
	head->left->right = new TreeNode(4);
	head->right->left = new TreeNode(7);
	head->left->left->left = new TreeNode(8);
	head->left->left->right = new TreeNode(9);
	head->left->right->left = new TreeNode(10);
	head->right->right->right = new TreeNode(12);
	head->right->right->left = new TreeNode(11);
	Solution s;
	if (s.isCBT(head))
		cout << "是CBT！\n";
	else
		cout << "不是CBT！\n";
	return 0;
}

如果不要求时间复杂度小于O（N），则可以通过遍历获得该数字，即O（N）.

结论: 如果树是完整的二叉树，则树的高度为h，节点数为2h-1

通过这种方式，可以使用公式直接计算全边. 其余节点可以递归找到.

每层仅遍历一个节点判断二叉排序树，每次都找到高度，所以复杂度为O（（logN）2）

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-220646-1.html