判断二叉树是否为排序二叉树
排序二叉树的递归定义： （1）空树。 （2）是由根节点、左子树和右子树组成。满足左子树上的所有节点的值都小于根节点的值，右子树上的所有节点的值都大于根节点的值。同时左子树和右子树都是排序二叉树（递归定义）。
老套路，还是根据定义来判断。首先如果一个树是空树，其必是一棵BST。如果不为空树，看是否满足条件二，如果满足则递归的看其两棵子树是否满足BST的定义。
代码实现：
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (!root) return true;
TreeNode *left = root->left;
TreeNode *right = root->right;
while (left) {
if (root->val <= left->val) return false;
left = left->right;
}
while (right) {
if (root->val >= right->val) return false;
right = right->left;
}
return isValidBST(root->left) && isValidBST(root->right);
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读