利用后序遍历,如果左右子树均为二叉搜索树,且根节点与左右子树根节点的大小符合二叉树要求,则为整个树是二叉搜索树:
// // Created by jt on 2020/8/23. // using namespace std; class Solution { public: /** * * @param root TreeNode类 * @return bool布尔型 */ bool isValidBST(TreeNode *root) { // write code here return postOrder(root); } bool postOrder(TreeNode *root) { if (!root) return true; if (!root->left && !root->right) return true; bool flag = false; if (!root->left) flag = root->val < root->right->val; if (!root->right) flag = root->val > root->left->val; if (root->left && root->right) flag = root->val > root->left->val && root->val < root->right->val; return postOrder(root->left) && postOrder(root->right) && flag; } };