LeetCode 98 Validate Binary Search Tree解题报告

By | 19/03/2018

【题目】:

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.

题目的意思应该就是给出一个二叉树判断是不是合法的BST树,给出的是层序遍历的结果。

【Code】:

class Solution {

private:

vector<int> v;

public:

boolisValidBST(TreeNode* root) {

if(root ==NULL||(root->left==NULL&& root->right==NULL)) returntrue;

inorder(root);

for(int i =1; i < v.size(); i++)

if(v[i] <= v[i-1]) returnfalse;

returntrue;

}

voidinorder(TreeNode* root) {

if(root ==NULL) return;

inorder(root->left);

v.push_back(root->val);

inorder(root->right);

}

};

【遇到的问题和解决办法】:

中序遍历一遍变得过程中判断后面的是不是比前面的大,如果大就是true,反之为false。

如果你觉得这篇文章有帮助,欢迎buy me a coffee

 

发表评论