LeetCode98.验证二叉搜索树

题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

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

示例 1：

输入：root = [2,1,3] 输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 10^4] 内-2^31 <= Node.val <= 2^31 - 1 思路 递归法

可以使用递归法中序遍历将二叉搜索树转变成一个数组，然后只要比较一下，这个数组是否是有序，就能判断是否为搜索二叉树，注意二叉搜索树中不能有重复元素。

更好思路是一边遍历一边判断值是不是递增的，此时需要记录前一个节点的值。

递归三部曲：

确定递归函数的参数和返回值。要定义一个longlong的全局变量，用来比较遍历的节点是否有序，因为后台测试数据中有int最小值，所以定义为longlong的类型，初始化为longlong最小值。确定终止条件。遇到空节点就可以终止，空节点也是搜索二叉树。确定单层递归的逻辑。中序遍历，一直更新maxVal（相当于前一个节点的值），一旦发现maxVal >= root->val，就返回false，注意元素相同时候也要返回false。 迭代法

可以用迭代法模拟二叉树的中序遍历。

代码

C++版：

递归法

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: // 递归法，中序遍历 long long maxVal = LONG_MIN; // f防止测试数据中有int最小值 TreeNode* pre = NULL; // 用来记录前一个节点，这样可以不用初始化最小值 bool isValidBST(TreeNode* root) { // 终止条件 if (root == NULL) return true; // 递归处理逻辑，中序遍历，验证遍历的元素是不是从小到大 bool left = isValidBST(root->left); if (pre != NULL && pre->val >= root->val) return false; pre = root; // 记录前一个节点 bool right = isValidBST(root->right); return left && right; } };

迭代法

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: // 迭代法，中序遍历 bool isValidBST(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur = root; TreeNode* pre = NULL; // 记录前一个节点 while (cur != NULL || !st.empty()) { if (cur != NULL) { st.push(cur); cur = cur->left; // 左 } else { cur = st.top(); // 中 st.pop(); if (pre != NULL && cur->val <= pre->val) return false; pre = cur; //保存前一个访问的结点 cur = cur->right; // 右 } } return true; } };

Python版：

递归法

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def __init__(self): self.pre = None # 用来记录前一个节点 def isValidBST(self, root: Optional[TreeNode]) -> bool: if root is None: return True left = self.isValidBST(root.left) if self.pre is not None and self.pre.val >= root.val: return False self.pre = root # 记录前一个节点 right = self.isValidBST(root.right) return left and right

迭代法

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: stack = [] cur = root pre = None # 记录前一个节点 while cur is not None or len(stack) > 0: if cur is not None: stack.append(cur) cur = cur.left # 左 else: cur = stack.pop() # 中 if pre is not None and cur.val <= pre.val: return False pre = cur # 保存前一个访问的结点 cur = cur.right # 右 return True 需要注意的地方

1.本题所存在的一些陷阱：

陷阱1：先入为主，写出了类似的代码

if (root->val > root->left->val && root->val < root->right->val) { return true; } else { return false; }

注意要比较的是左子树所有节点小于中间节点，右子树所有节点大于中间节点。所以以上代码的判断逻辑是错误的。

陷阱2：

样例中最小节点可能是int的最小值，如果这样使用最小的int来比较也是不行的，此时可以初始化比较元素为longlong的最小值。