首页 > 代码库 > Validate Binary Search Tree
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.
思路：对输入二叉树进行中序遍历，检查中序遍历序列是否递增。
1 class Solution { 2 public: 3 bool isValidBST( TreeNode *root ) { 4 prev = 0; 5 InOrder( root ); 6 } 7 private: 8 bool InOrder( TreeNode *node ) { 9 if( !node ) { return true; }10 if( !InOrder( node->left ) ) { return false; }11 if( prev && prev->val >= node->val ) { return false; }12 prev = node;13 return InOrder( node->right );14 }15 TreeNode *prev;16 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。