98.Validate Binary Search Tree

Tags: Medium Tree Depth-first Search

Links: https://leetcode.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.

Example 1:

    2
   / \
  1   3

Input: [2,1,3]
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

---

/**
 * 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) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (!root) return true; //空树肯定是没问题的

        bool flag = true;
        if (root -> left) {
            if (findMax(root -> left) >= root -> val) return false;
            flag = isValidBST(root -> left);
        }
        if (!flag) return false;

        if (root -> right) {
            if (findMin(root -> right) <= root -> val) return false;
            return isValidBST(root -> right);
        }

        return true;
    }

    int findMax(TreeNode *root)
    {
        int res = root -> val;
        if (root -> left) res = max(res, findMax(root -> left));
        if (root -> right) res = max(res, findMax(root -> right));
        return res;
    }

    int findMin(TreeNode *root)
    {
        int res = root -> val;
        if (root -> left) res = min(res, findMin(root -> left));
        if (root -> right) res = min(res, findMin(root -> right));
        return res;
    }
};

这道题是让判断给出的树是否满足二叉树，但是 比如[10,5,15,null,null,6,20]这个，如果只是检查与根节点连接的左右子节点，会输出true，实际上应该去检验左子树的最大值和右子树的最小值是否满足要求。

---

另一种思路就是考虑到是左<根<右，也就是不会存在相等的情况，那么完全可以利用中序遍历来检验遍历的结果是否有序，节省空间一点的做法就是利用线索二叉树来做。