?LeetCode刷題實戰(zhàn)98：驗證二叉搜索樹

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎知識和業(yè)務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！

今天和大家聊的問題叫做?驗證二叉搜索樹，我們先來看題面：

https://leetcode-cn.com/problems/validate-binary-search-tree/

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.

題意

• 節(jié)點的左子樹只包含小于當前節(jié)點的數(shù)。

• 節(jié)點的右子樹只包含大于當前節(jié)點的數(shù)。

• 所有左子樹和右子樹自身必須也是二叉搜索樹。

解題

class?Solution?{
public:
??long long maxValue = LLONG_MIN;//中序遍歷的當前最大值
??bool isValidBST(TreeNode* root) {
????if?(root == NULL){
??????return?true;
????}
????if?(!isValidBST(root->left)){//首先判斷左子樹是否是搜索二叉樹
??????return?false;
????}
????if?(root->val <= maxValue){//如果發(fā)現(xiàn)不大于之前的遇到的最大值，說明中序遍歷不是嚴格的遞增
??????return?false;
????}
????maxValue = root->val;//更新中序遍歷到此時，遇到的最大值
????if?(!isValidBST(root->right)){//首先判斷右子樹是否是搜索二叉樹
??????return?false;
????}
????return?true;
??}
};