Problem:
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
Input: [2,1,3]
Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
思路 1:
Solution I (C++):
public:
bool isValidBST(TreeNode* root) {
TreeNode *prev = NULL;
return is_valid(root, prev);
}
private:
bool is_valid(TreeNode* root, TreeNode* &top) {
if (root == NULL) return true;
if (!is_valid(root->left, top)) return false;
if (top && top->val >= root->val) return false;
top = root;
return is_valid(root->right, top);
}
性能:
Runtime: 16 ms Memory Usage: 20.6 MB
思路 2:
判断一个节点为根节点的左儿子还是右儿子,然后与根节点比较大小。
Solution II (C++):
public:
bool isValidBST(TreeNode* root) {
return isValidBST(root, NULL, NULL);
}
private:
bool isValidBST(TreeNode* node, TreeNode* is_lchild, TreeNode* is_rchild) {
if (!node) return true;
if (is_lchild && node->val >= is_lchild->val || is_rchild && node->val <= is_rchild->val) return false;
return isValidBST(node->left, node, is_rchild) && isValidBST(node->right, is_lchild, node);
}
性能:
Runtime: 20 ms Memory Usage: 20.6 MB
原文链接: https://www.cnblogs.com/dysjtu1995/p/12323683.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/330127
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!