赞
踩
给你一个二叉树的根节点
root
,判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3] 输出:true示例 2:
输入:root = [5,1,4,null,null,3,6] 输出:false 解释:根节点的值是 5 ,但是右子节点的值是 4 。提示:
- 树中节点数目范围在
[1, 104]
内-231 <= Node.val <= 231 - 1
方法1 递归:
思路:
这里推荐方法1 通用性更高,如果给你一个 LONG_MIN 或 LONG_MAX 的测试用例,那么方法2还是有数值边界问题。
时间复杂度:O(n) 在递归调用的时候二叉树的每个节点最多被访问一次,因此时间复杂度为 O(n)
空间复杂度:O(n) 其中 n 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间,所以这里需要额外的空间且该空间取决于递归的深度,即二叉树的高度。最坏情况下二叉树为一条链,树的高度为 n ,递归最深达到 n 层,故最坏情况下空间复杂度为 O(n)
Go版 方法1 & 方法2:
- /**
- * Definition for a binary tree node.
- * type TreeNode struct {
- * Val int
- * Left *TreeNode
- * Right *TreeNode
- * }
- */
-
- // 方法1 双指针比较法(pre和node),不需额外定义变量:math.MinInt64, math.MaxInt64:
- // 代码随想录视频题解:https://www.bilibili.com/video/BV18P411n7Q4/?spm_id_from=333.337.search-card.all.click&vd_source=2c268e25ffa1022b703ae0349e3659e4
- // 思路:中序遍历(左中右)为升序,每次比较左节点和根节点值,或比较根节点和右节点值
- func isValidBST(root *TreeNode) bool {
- var pre *TreeNode
-
- var dfs func(node *TreeNode) bool
- dfs = func(node *TreeNode) bool {
- if node == nil {
- return true // 空二叉树也是一颗特殊的BST
- }
-
- // 首次【不断向左子树递归】直至最后空节点
- l := dfs(node.Left)
-
- if pre != nil && node.Val <= pre.Val {
- return false
- }
-
- // 然后在自底向上【回溯】过程中,pre每次保存之前上一层栈空间中的根节点,即:
- // 当 node = root 时,pre = root.Left,满足:pre的值 < node值
- // 当 node = root.Right 时,pre = root,满足:pre的值 < node值
- pre = node
-
- r := dfs(node.Right)
-
- return l && r
- }
-
- return dfs(root)
- }
-
- // 方法2 官方题解(不推荐) 需额外定义变量:math.MinInt64, math.MaxInt64:
- func isValidBST(root *TreeNode) bool {
- return dfs(root, math.MinInt64, math.MaxInt64)
- }
-
- func dfs(node *TreeNode, lower, upper int) bool {
- if node == nil {
- return true // 空二叉树也是一颗特殊的BST
- }
-
- if node.Val <= lower || node.Val >= upper {
- return false
- }
-
- // 中序遍历:左中右
- // 不断向左子树递归时,当前节点值应大于整颗左子树,node.Val为上限 upper
- left := dfs(node.Left, lower, node.Val)
- // 不断向右子树递归时,当前节点值应小于整颗右子树,node.Val为下限 lower
- right := dfs(node.Right, node.Val, upper)
- return left && right
- }
C++版 方法1 & 方法3:
- // 方法1 递归:
- bool isValidBST(TreeNode* root) {
- return recurse(root, LONG_MIN, LONG_MAX);
- }
-
- bool recurse(TreeNode* root, long long low, long long high) { // low和hight:上届和下界
- // 递归终止条件
- if (root == NULL) // 空树也是特殊的二叉搜索树
- return true;
- if (root->val <= low || root->val >= high) // 如果当前节点值不在上下界内,false
- return false;
- // 下探到下一层
- return recurse(root->left, low, root->val) && recurse(root->right, root->val, high);
-
- // error:不能拆开写,左子树和右子树应当同时判断,而不是先后关系:
- // return recurse(root->left, low, root->val); // 左子树:上界为当前节点值(当前节点的左子树都小于当前节点值),下界不动
- // return recurse(root->right, root->val, high); // 右子树:下界为当前节点值(当前节点的右子树都大于当前节点值),上届不动
- }
-
-
- // 方法3 迭代法:
- // 思路:二叉搜索树的中序遍历为升序排列,故比较遍历到的当前节点与前一个节点的值是否满足:Val前 < val当前
- bool isValidBST(TreeNode* root) {
- stack<TreeNode*> st;
- // INT_MIN是先转换成long long类型然后再减去1的,也就是比所有的测试用例的值都要小了(测试用例的最小值是INT_MIN)
- // 中序遍历的结果应该是递增的,所以这样没错,左边一直小于右边就是true,包括最左边的数,它的左边肯定是最小值
- // 保留节点的上界与下界(因为当前节点值应大于左子树值,而不仅是左节点;当前节点值应大于右子树值,而不仅是右节点)
- long long leftChildVal = (long long)INT_MIN - 1; // 左孩子节点
-
- while (root != NULL || !st.empty())
- {
- while (root != NULL)
- {
- st.push(root);
- root = root->left;
- }
- if (!st.empty())
- {
- root = st.top();
- if (root->val <= leftChildVal) // // 若当前根节点值大于其右孩子,不满足二叉搜索树中序遍历值递增性质
- return false;
- leftChildVal = root->val;
- st.pop();
- root = root->right;
- }
- }
- return true;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。