判断是否为BST

发表于 | 分类于 | 评论数： | 阅读次数： | 阅读次数：

LeetCode Validate Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        stack<TreeNode*> stackNode;
        TreeNode* prev = nullptr;
        while (root != nullptr || !stackNode.empty()) {
            while (root != nullptr) {
                stackNode.push(root);
                root = root->left;
            }
            root = stackNode.top();
            stackNode.pop();
            if (prev != nullptr && root->val <= prev->val) {
                return false;
            }
            prev = root;
            root = root->right;
        }
        return true;
    }
};
  • 平衡二叉树， node左侧所有节点的value小于node， 右侧所有节点的value大于node， 同时左右子树也都是BST。
  • 使用中序遍历的方式解决。
  • prev初始化为nullptr，后面再让prev指向当前处理的节点root。这个技巧在之前的flatten binary tree 中也有使用。
0%