高端品牌网站开发,描述网站建设规范方法,贵阳做网站设计,怎么做广告推广1. 题目
实现一个函数#xff0c;检查一棵二叉树是否为二叉搜索树。
示例 1:
输入:2/ \1 3
输出: true示例 2:
输入:5/ \1 4/ \3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 #xff0c;但是其右子节点值为 4 。2. 解题
该题要求严格…1. 题目
实现一个函数检查一棵二叉树是否为二叉搜索树。
示例 1:
输入:2/ \1 3
输出: true示例 2:
输入:5/ \1 4/ \3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 但是其右子节点值为 4 。2. 解题
该题要求严格不允许相等中序遍历即可
class Solution {
public:bool isValidBST(TreeNode* root) {stackTreeNode* stk;TreeNode* tp, *prev NULL;while(root || !stk.empty()){while(root){stk.push(root);root root-left;}tp stk.top();stk.pop();if(prev ! NULL prev-val tp-val)return false;prev tp;root tp-right;}return true;}
};递归返回子树的最小值和最大值供上一层判断
class Solution {
public:bool isValidBST(TreeNode* root) {if(!root)return true;bool ans true;check(root,ans);return ans;}vectorint check(TreeNode* root, bool ans){if(!root || ans false)return {};vectorint l, r;l check(root-left, ans);r check(root-right, ans);if(l.empty() r.empty())return {root-val, root-val};else if(!l.empty() r.empty()){if(l[1] root-val)ans false;return {l[0], root-val};}else if(l.empty() !r.empty()){if(r[0] root-val)ans false;return {root-val, r[1]};}else{if(l[1] root-val || r[0] root-val)ans false;return {l[0], r[1]};} }
};or
class Solution {bool ans true;long prevVal LONG_MIN;
public:bool isValidBST(TreeNode* root) {if(!root || ans false)return true;isValidBST(root-left);if(root-val prevVal)ans false;elseprevVal root-val;isValidBST(root-right);return ans;}
};
