Validate Binary Search Tree

原題鏈接Validate Binary Search Tree

判斷一顆樹(shù)是否是二叉搜索樹(shù)，一棵樹(shù)是BST需要滿足

• 一個(gè)節(jié)點(diǎn)的值大于它左子樹(shù)所有節(jié)點(diǎn)的值
• 一個(gè)節(jié)點(diǎn)的值小于它右子樹(shù)所有節(jié)點(diǎn)的值
• 左右子樹(shù)也必須是二叉搜索樹(shù)

所以只需要遍歷每個(gè)節(jié)點(diǎn)，判斷

• 該節(jié)點(diǎn)值是否大于左子樹(shù)的最大值
• 該節(jié)點(diǎn)值是否小于右子樹(shù)的最小值

代碼如下

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:bool isValidBST(TreeNode* root) {if(!root) return true;//大于左子樹(shù)的最大值TreeNode* leftNode = root->left;while(leftNode){if(root->val <= leftNode->val)return false;leftNode = leftNode->right;}//小于右子樹(shù)的最小值TreeNode* rightNode = root->right;while(rightNode){if(root->val >= rightNode->val)return false;rightNode = rightNode->left;}if(isValidBST(root->left) && isValidBST(root->right))return true;elsereturn false;} };

總結(jié)

以上是生活随笔為你收集整理的每天一道LeetCode-----判断某棵树是否是二叉搜索树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。