Menu

Subscribe

LeetCode 98 [Validate Binary Search Tree]

ShuyuFang on Leetcode

题目链接

题目描述

  • 判断给定的二叉树是不是二叉排序树，假定二叉排序树满足以下条件：
    1. 任意一个结点的左子树的所有结点的值都比该结点小。
    2. 任意一个结点的右子树的所有结点的值都比该结点大。
    3. 左子树和右子树都是二叉排序树（递归定义）。

解题思路

  1. 根据二叉排序树的定义，从根结点出发，验证以每一个结点为根的树是否满足条件。
  2. 对每一个被遍历的结点，若左子结点不为空，则查找左子树的所有结点的最大值，若该值不小于当前结点的值，则说明当前树不是二叉排序树，否则继续查找右子树的所有结点的最小值，若该值不大于当前结点的值，则同样说明当前树不是二叉排序树。
  3. 实际代码实现使用递归的方式，最大值被初始化为整型的最小值，最小值被初始化为整型的最大值，由上层调用时传入。

C++代码

/**
 * 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) {
        if (!root) {
            return true;
        }
        int max = INT_MIN;
        int min = INT_MAX;
        return travel(root, max, min);
    }
    
    bool travel(TreeNode* node, int& max, int& min) {
        max = node->val > max ? node->val : max;
        min = node->val < min ? node->val : min;
        
        int tmpmax, tmpmin;
        
        if (node->left) {
            tmpmax = INT_MIN;
            tmpmin = INT_MAX;
            if (!travel(node->left, tmpmax, tmpmin)) {
                return false;
            } else if (tmpmax >= node->val) {
                return false;
            }
            max = tmpmax > max ? tmpmax : max;
            min = tmpmin < min ? tmpmin : min;
        }
        
        if (node->right) {
            tmpmax = INT_MIN;
            tmpmin = INT_MAX;
            if (!travel(node->right, tmpmax, tmpmin)) {
                return false;
            } else if (tmpmin <= node->val) {
                return false;
            }
            max = tmpmax > max ? tmpmax : max;
            min = tmpmin < min ? tmpmin : min;
        }
        
        return true;
    }
};