对应letecode链接：
力扣
题目描述：
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1
解题思路：
1.当前节点的值是其左子树的值的上界（最大值）
2.当前节点的值是其右子树的值的下界（最小值）
所以我们在此引入上界与下界，用以保存之前的节点中出现的最大值与最小值
在每棵子树，root 都是左子树的上界，是右子树的下界。只有当这两者同时成立时，才可能确保是一颗二叉搜索树。
对应代码：
class Solution {
public:
bool isValidBST(TreeNode* root) {
return traversal(root,LONG_LONG_MIN,LONG_LONG_MAX);//由于题目说节点的值可以取到整型最大或者最小所以我们用long long
}
bool traversal(TreeNode*root,long long min,long long max)
{
if(root==nullptr)//空树为true
{
return true;
}
if(root->val<=min||root->val>=max)//不合法
{
return false;
}
bool Leftret= traversal(root->left,min,(long long)(root->val));//检查左子树
if(!Leftret)return false;
bool Rightret=traversal(root->right,(long long)(root->val),max);//检查右子树
return Rightret;
}
};
当然我们还可以使用中序遍历：
定义一个类似于全局变量的preval，先检查左子树是不是搜索二叉树。当递归完左子树时判断单前节点的值是否小于等于preval如果是则返回false,不是则把当前节点的值给preval.
对应代码：
class Solution {
public:
long long preval=LONG_LONG_MIN;
bool isValidBST(TreeNode* root) {
if(!root)return true;
bool isLeftBST=isValidBST(root->left);//检查左子树是不是
if(!isLeftBST){
return false;
}
if(root->val<=preval){//不合法
return false;
}else{
preval=root->val;
}
return isValidBST(root->right);//检查右子树即可；
}
};
迭代法：
由于搜索二叉树的中序遍历是有序的所以我们可以比较相邻的两个数看是不是有序的。比较完整棵树之后结果就出来了
class Solution {
public:
bool isValidBST(TreeNode* root) {
TreeNode*pre=nullptr;
stackstk;
TreeNode*cur=root;
while(!stk.empty()||cur){
while(cur){
stk.push(cur);
cur=cur->left;
}
auto node=stk.top();
stk.pop();
if((pre!=nullptr)&&node->val<=pre->val){//前面一个比后面一个大违法搜索二叉树的规则
return false;
}
pre=node;
cur=node->right;
}
return true;
}
};
平衡二叉树
对应letecode链接：
力扣
题目描述：
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：输入：root = []
输出：true提示：
树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104
解题思路：
1.对当前节点，分别求解左子树和右子树的深度，判断左右子树的高度差是否<=1。
2.利用了104题中求解二叉树的深度的方法
3.然后再对当前节点的左子树和右子树做同样操作。
对应代码：
class Solution {
public:
int getdepth(TreeNode*root) {//求高度
if(root==nullptr)
return 0;
int len1=getdepth(root->left);
int len2=getdepth(root->right);
return len1>len2?len1+1:len2+1;
}
bool isBalanced(TreeNode* root) {
if(root==nullptr)
return true;//空树为true;
return abs(getdepth(root->left)-getdepth(root->right))<2&&isBalanced(root->left)&&isBalanced(root->right);
}
};
但是这样时间复制度就非常的高为0(N^2)重复计算了很多。因此我们可以考虑后序遍历定义一个变量flag初始值为true，在检查子树的过程中判断平衡性，如果已经不平衡就终止递归
对应代码：
class Solution {
public:
bool flag=true;
int TreeDepth(TreeNode*root){
if(!root||!flag)return 0;//！flag是为了终止递归返回什么都不重要
int leftDepth=TreeDepth(root->left);//求左子树的高度
int rightDepth=TreeDepth(root->right);//求右子树的高度
if(abs(leftDepth-rightDepth)>1){//不平衡
flag=false;
}
return max(leftDepth,rightDepth)+1;
}
bool isBalanced(TreeNode* root) {
TreeDepth(root);
return flag;
}
};
或者这样也是可以的：
class Solution {
public:
bool _isBalanced(TreeNode*root,int&ph){
if(!root){
ph=0;
return true;
}
int leftHight=0;
if(!_isBalanced(root->left,leftHight))return false;
int rightHight=0;
if(!_isBalanced(root->right,rightHight))return false;
ph=max(leftHight,rightHight)+1;
return abs(leftHight-rightHight)<2;
}
bool isBalanced(TreeNode* root) {
int _hight=0;
return _isBalanced(root,_hight);
}
};
判断一颗树是否为满二叉树
思路：
将树的节点都入队
然后按照满二叉树每一层的节点个数控制节点出队 如果每一层都满足节点数控制 那么为满二叉树
只要存在一层不满足出队数量 就不是满二叉树
对应代码：
bool isFullTree(TreeNode*root){
if(!root)return false;//空树不是完全二叉树
int num=1;//第一层一个节点
queueq;
q.push(root);
while(!q.empty()){
int i;
for( i=0;ileft){
q.push(node->left);
}
if(node->right){
q.push(node->right);
}
}
}//只要有一层出队的个数小于num那么他就不是满二叉树
if(i
对应完全二叉树的代码和解题思路在我的二叉树基础篇有铁子们可以取那里找找。
