【408DS算法题】033基础-判断二叉树是否是二叉排序树

本文主要是介绍【408DS算法题】033基础-判断二叉树是否是二叉排序树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Index

- 题目
- 分析实现
- 总结

题目

给定二叉树的根节点root，判断该二叉树是否是二叉排序树。

分析实现

二叉排序树（BST/二叉搜索树）：对于每个节点，其左子树中所有节点的值都小于当前结点的值，其右子树中所有节点的值都大于当前结点的值；左子树和右子树本身也是二叉搜索树。

在二叉排序树的定义中含有着递归的思想 - “左子树和右子树本身也是二叉搜索树”，因此可以使用递归函数来尝试实现。

具体实现如下：

// 判断BST工具函数
bool isBSTUtil(BTNode* cur, int min, int max){if(cur==NULL)return true;if(cur->val<min || cur->val>max) return false;return isBSTUtil(cur->left, min, cur->val) && isBSTUtil(cur->right, cur->val, max);
}// 判断二叉搜索树
bool isBST(BTNode *root){return isBSTUtil(root, INT_MIN, INT_MAX);
}

总结

以上就是利用先序遍历判断二叉排序树的实现，同理也可以利用中序遍历实现判断BST的工具函数（欢迎在评论区讨论交流！）。

特别注意的是，本题有一个常见的错误思路，就是依次判断每个结点：

bool isBST(BTNode *root){if(root==nullptr) return true;if(root->left && root->left->val>=root->val)return false;if(root->right && root->right->val<=root->val)return false;return isBST(root->left) && isBST(root->right);
}