作文以记之~验证二叉搜索树

本篇博客是力扣上 98. 验证二叉搜索树 题的题解&＃xff0c;也是一个 DFS 的练习题&＃xff0c;只要按照DFS的逻辑来&＃xff0c;整个coding过程不难&＃xff0c;挺有意思的~

GitHub上相关内容可 点击此处 进行查看&＃xff01;

2.1 方法1 ~ 利用DFS

2.1.1 思路

只要所给二叉树不满足以下条件&＃xff0c;则不为二叉搜索树&＃xff0c;故而可以按照以下条件设置合理判断即可&＃xff01;
如果该二叉树的左子树不为空&＃xff0c;则左子树上所有节点的值均小于它的根节点的值&＃xff1b; 若它的右子树不空&＃xff0c;则右子树上所有节点的值均大于它的根节点的值&＃xff1b;它的左右子树也为二叉搜索树。

2.1.2 程序代码

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isValidTree(TreeNode* root, long minval, long maxval){if(root &＃61;&＃61; nullptr)return true;if(root->val >&＃61; maxval || root->val <&＃61; minval)return false;return isValidTree(root->left,minval,root->val) && isValidTree(root->right,root->val,maxval);}bool isValidBST(TreeNode* root) {return isValidTree(root,LONG_MIN,LONG_MAX);}
};


2.2 方法2 ~ 利用迭代

2.2.1 思路

此处思路就是将上面方法的递归给展开实现&＃xff0c;具体看代码吧

2.1.2 程序代码

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isValidBST(TreeNode* root) {stack<TreeNode*> st;long minval &＃61; LONG_MIN;while(!st.empty() || root !&＃61; nullptr){while(root){st.push(root);root &＃61; root->left;}root &＃61; st.top();st.pop();if(root->val <&＃61; minval)return false;minval &＃61; root->val;root &＃61; root->right;}return true;}
};