题目
判断一个树是否是搜索二叉树(BST).
BST满足以下条件:
所有左子节点小于父节点, 所有右子节点大于父节点
所有子树都是BST
Input: [2,1,3]
2
/ \
1 3
Output: true
Input: [5,1,4,null,null,3,6]
5
/ \
1 4
/ \
3 6
Output: true
思路
通过中序遍历进行输出节点, 通过栈存储值, 如果最后值大于1即为非BST.
stack<int> s;
void inorderRead(TreeNode* root) {
if (root == nullptr) return;
inorderRead(root->left);
if (s.empty()) {
s.push(root->val);
} else {
if ((s.top() < root->val)) {
s.pop();
}
s.push(root->val);
}
inorderRead(root->right);
}
bool isValidBST(TreeNode* root) {
inorderRead(root);
return s.size() <= 1;
}
总结
熟练掌握二叉树的遍历, 巧妙使用stack等容器适配器.
