Validate Binary Search Tree--LeetCode

╰半橙微兮° 2022-08-05 14:18 161阅读 0赞

# 题目： #

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

*  The left subtree of a node contains only nodes with keys less than the node's key.
 *  The right subtree of a node contains only nodes with keys greater than the node's key.
 *  Both the left and right subtrees must also be binary search trees.

思路：使用递归，或者中序遍历记录前向节点的值

bool isValidBST(BinTree* root)
    {
    	if(root ==NULL)
    		return true;
    	else
    	{
    		
    		if(root->right != NULL&& root->left == NULL)
    			return  isValidBST(root->right)&& root->value <root->right->value;
    		else if(root->left != NULL && root->right == NULL)
    			return isValidBST(root->left)&& root->value > root->left->value;
    		else if(root->left != NULL && root->right != NULL)
    			return isValidBST(root->right)&&isValidBST(root->left)&& root->value >root->left->value && root->value < root->right->value;
    		else
    			return true;	
    			
    	}
    }

第二种方法和中序遍历非常相似，因为中序遍历的结果是有序的，记录前序节点，当前节点和前序节点相比较即可

BinTree* cur=NULL,*pre= NULL;
    bool isValidBSTSecond(BinTree* root)
    {
    	if(root== NULL)
    		return true;
    	bool left = isValidBSTSecond(root->left);
    	
    	if(pre == NULL)
    		pre = root;
    	cur = root;
    	if(cur != pre && pre->value > cur->value)
    		return false;		
    	pre = cur;
    	
    	bool right =isValidBSTSecond(root->right);
    	return right&&left;
    	
    	
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，161人围观）

还没有评论，来说两句吧...

相关阅读

相关 98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST

Bertha 。/ 2023年07月03日 02:48/ 0 赞/ 16 阅读

相关 leetcode 98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST

落日映苍穹つ/ 2022年08月21日 02:26/ 0 赞/ 126 阅读

相关 leetCode 98-Validate Binary Search Tree

题目链接：https://leetcode.com/problems/validate-binary-search-tree/ 就是判断一个给定的二叉树是否为二叉查找树。

清疚/ 2022年08月07日 10:58/ 0 赞/ 173 阅读

相关 Validate Binary Search Tree--LeetCode

题目： Given a binary tree, determine if it is a valid binary search tree (BST). Ass

╰半橙微兮°/ 2022年08月05日 14:18/ 0 赞/ 162 阅读

相关 LeetCode-Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST

川长思鸟来/ 2022年08月04日 00:59/ 0 赞/ 13 阅读

相关 [Leetcode][python]Validate Binary Search Tree

题目大意判断一棵树是否为二叉搜索树解题思路想到了中序遍历整棵树，那么结果应该是升序的。直接套用之前的中序遍历代码，稍加修改即可。网上的答案很多都在分析

约定不等于承诺〃/ 2022年06月11日 05:58/ 0 赞/ 158 阅读

相关 98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST

落日映苍穹つ/ 2022年03月07日 03:42/ 0 赞/ 194 阅读

相关 98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST

川长思鸟来/ 2022年03月07日 03:42/ 0 赞/ 178 阅读

相关 98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST

ゝ一世哀愁。/ 2022年03月07日 03:40/ 0 赞/ 171 阅读

相关 Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST

刺骨的言语ヽ痛彻心扉/ 2021年12月17日 10:35/ 0 赞/ 216 阅读