深度优先遍历
- 思路:
- 根据二叉搜索树特性,通过中序遍历得到有序序列,验证序列是否有序来判断;
- 中序遍历使用栈通过深度优先遍历;
/**
* 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) {
std::stack<TreeNode*> stk;
long long pre = (long long)(INT_MIN) - 1;
TreeNode* node = root;
while ((node != nullptr) || (!stk.empty())) {
while (node != nullptr) {
stk.push(node);
node = node->left;
}
node = stk.top();
stk.pop();
if (node->val <= pre) {
return false;
}
pre = node->val;
node = node->right;
}
return true;
}
};