【LeetCode】74. Validate Binary Search Tree

xiaoxiao2021-03-01  26

题目描述(Medium)

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.

题目链接

https://leetcode.com/problems/validate-binary-search-tree/description/

Example 1:

Input:     2    / \   1   3 Output: true

Example 2:

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

算法分析

中序遍历后判断序列的大小关系或者直接遍历,判断根节点与左右子树的关系。

提交代码:

class Solution { public: bool isValidBST(TreeNode* root) { return isValidBST(root, LONG_MIN, LONG_MAX); } bool isValidBST(TreeNode* root, long lower, long upper) { if (root == nullptr) return true; return root->val > lower && root->val < upper && isValidBST(root->left, lower, root->val) && isValidBST(root->right, root->val, upper); } };

 

转载请注明原文地址: https://www.6miu.com/read-4200120.html

最新回复(0)