pic

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.
confused what "{1,#,2,3}" means?

分析

题意是：验证二叉树是否是二叉搜索树

首先需要知道什么是二叉搜索树：

  • 左节点小于根节点，右节点大于根节点；
  • 左、右子树都是二叉搜索树；
根据二叉树的定义来看，第一条规则很容易判断，但是第二条规则，如何判断？
很简单，只要左子树的最右节点小于根节点，右子树的最左节点大于根节点即可。

Code

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    /* 
     * 二叉搜索树的特点是左节点小于根节点，右子树大于根节点；左右子树也是二叉搜索树
     * 
     * */
    bool isValidBST(TreeNode *root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(!root)   return true;
        if(!(root->left) && !(root->right))     return true;

        TreeNode *mostLeftOfRchild , *mostRightOfLchild;
        mostRightOfLchild = root->left;
        while(mostRightOfLchild && (mostRightOfLchild->right) )
            mostRightOfLchild = mostRightOfLchild->right;
        if(mostRightOfLchild&&(mostRightOfLchild->val >= root->val) )
            return false;
        mostLeftOfRchild = root->right;
        while(mostLeftOfRchild && (mostLeftOfRchild->left) )
            mostLeftOfRchild = mostLeftOfRchild->left;
        if(mostLeftOfRchild&&(mostLeftOfRchild->val <= root->val) )
            return false;   
        return isValidBST(root->left)&&isValidBST(root->right);
    }
};

pic