二叉树:我是不是一棵二叉搜索树

学习完二叉搜索树的特性了 , 那么就验证一波
98.验证二叉搜索树给定一个二叉树 , 判断其是否是一个有效的二叉搜索树 。
假设一个二叉搜索树具有如下特征:

  • 节点的左子树只包含小于当前节点的数 。
  • 节点的右子树只包含大于当前节点的数 。
  • 所有左子树和右子树自身必须也是二叉搜索树 。

二叉树:我是不是一棵二叉搜索树文章插图
思路要知道中序遍历下 , 输出的二叉搜索树节点的数值是有序序列 。
有了这个特性 , 「验证二叉搜索树 , 就相当于变成了判断一个序列是不是递增的了 。 」
递归法可以递归中序遍历将二叉搜索树转变成一个数组 , 代码如下:
vector vec;void traversal(TreeNode* root) {if (root == NULL) return;traversal(root->left);vec.push_back(root->val); // 将二叉搜索树转换为有序数组traversal(root->right);}然后只要比较一下 , 这个数组是否是有序的 , 「注意二叉搜索树中不能有重复元素」 。
traversal(root);for (int i = 1; i < vec.size(); i++) {// 注意要小于等于 , 搜索树里不能有相同元素if (vec[i] <= vec[i - 1]) return false;}return true;整体代码如下:
class Solution {private:vector vec;void traversal(TreeNode* root) {if (root == NULL) return;traversal(root->left);vec.push_back(root->val); // 将二叉搜索树转换为有序数组traversal(root->right);}public:bool isValidBST(TreeNode* root) {vec.clear(); // 不加这句在leetcode上也可以过 , 但最好加上traversal(root);for (int i = 1; i < vec.size(); i++) {// 注意要小于等于 , 搜索树里不能有相同元素if (vec[i] <= vec[i - 1]) return false;}return true;}};以上代码中 , 我们把二叉树转变为数组来判断 , 是最直观的 , 但其实不用转变成数组 , 可以在递归遍历的过程中直接判断是否有序 。
这道题目比较容易陷入两个陷阱:
  • 陷阱1
「不能单纯的比较左节点小于中间节点 , 右节点大于中间节点就完事了」 。
写出了类似这样的代码:
if (root->val > root->left->val } else {return false;}我们要比较的是 左子树所有节点小于中间节点 , 右子树所有节点大于中间节点 。 所以以上代码的判断逻辑是错误的 。
例如:[10,5,15,null,null,6,20] 这个case:
二叉树:我是不是一棵二叉搜索树文章插图
节点10小于左节点5 , 大于右节点15 , 但右子树里出现了一个6 这就不符合了!
  • 陷阱2
样例中最小节点 可能是int的最小值 , 如果这样使用最小的int来比较也是不行的 。
此时可以初始化比较元素为longlong的最小值 。
问题可以进一步演进:如果样例中根节点的val 可能是longlong的最小值 又要怎么办呢?文中会解答 。
了解这些陷阱之后我们来看一下代码应该怎么写:
递归三部曲:
  • 确定递归函数 , 返回值以及参数
要定义一个longlong的全局变量 , 用来比较遍历的节点是否有序 , 因为后台测试数据中有int最小值 , 所以定义为longlong的类型 , 初始化为longlong最小值 。
注意递归函数要有bool类型的返回值 ,我们在二叉树:递归函数究竟什么时候需要返回值 , 什么时候不要返回值? 中讲了 , 只有寻找某一条边(或者一个节点)的时候 , 递归函数会有bool类型的返回值 。
其实本题是同样的道理 , 我们在寻找一个不符合条件的节点 , 如果没有找到这个节点就遍历了整个树 , 如果找到不符合的节点了 , 立刻返回 。