脚本宝典收集整理的这篇文章主要介绍了【leetcode】98. Validate Binary Search Tree 二叉树是否是中序有序的,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
1. 题目
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.
Example 1:
2
/
1 3
Binary tree [2,1,3], return true.
Example 2:
1
/
2 3
Binary tree [1,2,3], return false.
2. 思路
递归测试,满足的条件是左、右子树各自满足,且跟大于左子树max,跟小于又子树min。
3. 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
int min, max;
return isValidBST(root, &min, &max);
}
bool isValidBST(TreeNode* root, int* min, int* max) {
if (root == NULL) { return true; }
*min = *max = root->val;
int tmp;
if (root->left != NULL) {
if (!isValidBST(root->left, min, &tmp) || tmp >= root->val) { return false; }
}
if (root->right != NULL) {
if (!isValidBST(root->right, &tmp, max) || tmp <= root->val) { return false;}
}
return true;
}
};
以上是脚本宝典为你收集整理的【leetcode】98. Validate Binary Search Tree 二叉树是否是中序有序的全部内容,希望文章能够帮你解决【leetcode】98. Validate Binary Search Tree 二叉树是否是中序有序的所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。