首页 > 代码库 > leetcode 98. Validate Binary Search Tree
leetcode 98. Validate Binary Search Tree
最简单的想法，中序遍历二叉树：
- 递归中序遍历二叉树，得到一个中序遍历的序列
- 判断这个序列是不是有序
class Solution {public: void midTree(TreeNode * root, vector<int> & list) { if(root->left==NULL&&root->right==NULL) { list.push_back(root->val); return; } if(root->left) midTree(root->left,list); list.push_back(root->val); if(root->right) midTree(root->right,list); } bool isValidBST(TreeNode* root) { vector<int> list; if(root==NULL) return true; midTree(root,list); for(int i=0;i<list.size()-1;i++) { cout<<list[i]<<endl; if(list[i+1]<=list[i]) return false; } return true; }};
或者直接判断：
- 中序遍历，后面的节点要比前面遍历的节点值大
class Solution { // make sure it meets the BST not only at this level, // but also previous level // in-order access could produce a ascending order list // DFS bool helper(TreeNode * root) { if (root == NULL) { return true; } if (!helper(root->left)) { return false; } if (prev != NULL && prev->val >= root->val) { return false; } prev = root; return helper(root->right); }public: TreeNode* prev = NULL; bool isValidBST(TreeNode* root) { return helper(root); }};
leetcode 98. Validate Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。