首页 > 代码库 > [Leetcode][BST][Validate Binary Search Tree]
[Leetcode][BST][Validate Binary Search Tree]
判断一颗树是不是二分查找树，非常经典基础的一个算法。
我很久之前第一次做的时候，是先求出来了树的前序遍历的结果，然后判断这个数组排序后是否和排序前相同，还要判断重复虾米的，很纠结的一种做法。
后来思考了一下怎么用递归的思路做，觉得应该根据定义返回两个子树的最大值和最小值，写了一会代码，发现好麻烦，不太对的样子。
后来看了题解，发现是用了一种反向的思维，把上下界从树的顶端传下去，而不是自下而上的约束。作者太机智了。
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 bool validate(TreeNode *root, int low, int high) {13 if (root == NULL) {14 return true;15 }16 if (root->val <= low || root->val >= high) {17 return false;18 }19 return validate(root->left, low, root->val) 20 && validate(root->right, root->val, high);21 }22 bool isValidBST(TreeNode *root) {23 if (root == NULL) {24 return true;25 } 26 return validate(root, INT_MIN, INT_MAX);27 }28 };
中间WA了两次，一次是由于把空树返回了false，另外一次是没有去掉val相等的情况。
树的问题，想清楚了很快就能写出代码，而且一次AC。想不清楚的话，就容易把自己绕进去。。状态很重要。。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。