算法
中序迭代遍历二叉树。
时间复杂度: O(n)
空间复杂度: O(h)
C++
class Solution {
public:
static bool isValidBST(TreeNode *node) {
TreeNode *prev = NULL;
stack<TreeNode *> stk;
while (node || !stk.empty()) {
while (node) {
stk.push(node);
node = node->left;
}
node = stk.top();
stk.pop();
if (prev && prev->val >= node->val) {
return false;
}
prev = node;
node = node->right;
}
return true;
}
};
Java
class Solution {
public static boolean isValidBST(TreeNode node) {
TreeNode prev = null;
List<TreeNode> stk = new ArrayList<>();
while (node != null || !stk.isEmpty()) {
while (node != null) {
stk.add(node);
node = node.left;
}
node = stk.get(stk.size() - 1);
stk.remove(stk.size() - 1);
if (prev != null && prev.val >= node.val) {
return false;
}
prev = node;
node = node.right;
}
return true;
}
}
Python3
class Solution:
def isValidBST(self, node: TreeNode) -> bool:
prev = None
stk = []
while node or stk:
while node:
stk.append(node)
node = node.left
node = stk.pop()
if prev and prev.val >= node.val:
return False
prev = node
node = node.right
return True