Validate Binary Search Tree - LeetCode
发布时间:2020-12-14 04:37:01 所属栏目:大数据 来源:网络整理
导读:目录 题目链接 注意点 解法 小结 题目链接 Validate Binary Search Tree - LeetCode 注意点 不要访问空结点 结点的val有可能会正好等于int的最大取值范围 解法 解法一:因为这里的二叉搜索树定义是说重复的数字也不算,所以可以用中序遍历,然后判断是否是递
目录
题目链接Validate Binary Search Tree - LeetCode 注意点
解法解法一:因为这里的二叉搜索树定义是说重复的数字也不算,所以可以用中序遍历,然后判断是否是递增的。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x),left(NULL),right(NULL) {} * }; */ class Solution { public: typedef TreeNode* node; void inOrder(node n,vector<long>& nums) { if(!n) return; inOrder(n->left,nums); nums.push_back(n->val); inOrder(n->right,nums); } bool isValidBST(TreeNode* root) { vector<long> nums; inOrder(root,nums); int i,n = nums.size(); for(i = 0;i < n;i++) { if(i+1 < n && nums[i] >= nums[i+1]) return false; } return true; } }; 解法二:利用它本身的性质来做,即左<根<右,初始化时带入long最大值和最小值,在递归过程中换成它们自己的节点值,用long代替int就是处理刚好val是int最大值的时候。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x),right(NULL) {} * }; */ class Solution { public: typedef TreeNode* node; bool dfs(node n,long min,long max) { if(!n) return true; if(n->val <= min || n->val >= max) return false; return dfs(n->left,min,n->val) && dfs(n->right,n->val,max); } bool isValidBST(TreeNode* root) { return dfs(root,LONG_MIN,LONG_MAX); } }; 小结
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |