LeetCode-98. Validate Binary Search Tree

LeetCode-98. 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 keysless thanthe node's key.The right subtree of a node contains only nodes with keysgreater thanthe node's key.Both the left and right subtrees must also be binary search trees.

Example 1:

2 / \ 1 3Input: [2,1,3]Output: true

Example 2:

5 / \ 1 4 / \ 3 6Input: [5,1,4,null,null,3,6]Output: falseExplanation: The root node's value is 5 but its right child's value is 4.

题解：

中序遍历看序列是否有序即可。

class Solution {public: void visitTree(TreeNode* root, vector &res) { if (root != NULL) { visitTree(root->left, res); res.push_back(root->val); visitTree(root->right, res); } } bool isValidBST(TreeNode* root) { vector res; if (root == NULL) { return true; } visitTree(root, res); for (int i = 0; i < res.size() - 1; i++) { if (res[i] >= res[i + 1]) { return false; } } return true; }};

或者判断每个叶节点是否合法

class Solution {public: bool validate(TreeNode* root, TreeNode* min, TreeNode* max) { if (root == NULL) { return true; } else if ((min != NULL && root->val <= min->val) || (max != NULL && root->val >= max->val)) { return false; } return validate(root->left, min, root) && validate(root->right, root, max); } bool isValidBST(TreeNode* root) { return validate(root, NULL, NULL); }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。