室内设计网站源码下载,机械设备网站,建设银行广西分行网站,新能源汽车价格给你一个二叉树的根节点 root #xff0c;判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下#xff1a; 节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 示例 1#xff1a; 输入判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下 节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 示例 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 递归通过形参改变取值范围
class Solution {
public:bool func(TreeNode *root,long long lower,long long upper){if(rootnullptr)return true;if(root-vallower||root-valupper)return false;return func(root-left,lower,root-val)func(root-right,root-val,upper);}bool isValidBST(TreeNode* root) {return func(root,LONG_MIN,LONG_MAX);}
};
递归(中序遍历)通过比较当前节点值和上一个节点值
中序遍历是左中右的顺序刚刚好搜索二叉树的特点是左中右。
class Solution {
public:TreeNode *prenullptr;bool isValidBST(TreeNode* root) {if(rootnullptr)return true;bool leftisValidBST(root-left);if(pre!nullptrpre-valroot-val)return false;preroot;bool rightisValidBST(root-right);return leftright;}
};
