互聯(lián)網(wǎng)經(jīng)典算法之驗(yàn)證二叉搜索樹(shù)
本文轉(zhuǎn)載自微信公眾號(hào)「程序員小熊」，作者Dine 。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序員小熊公眾號(hào)。
前言
大家好，我是來(lái)自于華為的程序員小熊。今天給大家?guī)?lái)一道與二叉樹(shù)相關(guān)的面試高頻題，這道題在半年內(nèi)被谷歌、字節(jié)、微軟和亞馬遜等大廠作為面試題，即力扣上的第98題-驗(yàn)證二叉搜索樹(shù)。
本文主要介紹遞歸和深度優(yōu)先搜索兩種方法來(lái)解答此題，供大家參考，希望對(duì)大家有所幫助。
驗(yàn)證二叉搜索樹(shù)
給你一個(gè)二叉樹(shù)的根節(jié)點(diǎn) root ，判斷其是否是一個(gè)有效的二叉搜索樹(shù)。
有效二叉搜索樹(shù)定義如下：
節(jié)點(diǎn)的左子樹(shù)只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。
節(jié)點(diǎn)的右子樹(shù)只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)。
所有左子樹(shù)和右子樹(shù)自身必須也是二叉搜索樹(shù)。
示例 1
示例 2 及提示
二叉搜索樹(shù)
題目已提示有效二叉搜索樹(shù)的定義如下：
- 節(jié)點(diǎn)的左子樹(shù)只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。
- 節(jié)點(diǎn)的右子樹(shù)只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)。
- 所有左子樹(shù)和右子樹(shù)自身必須也是二叉搜索樹(shù)。
舉例
例 1
例1
例 2
例 3
判斷二叉搜索樹(shù)
針對(duì)上面的舉例，根據(jù)二叉搜索樹(shù)的判斷方法，對(duì)上面的例子是否是二叉搜索樹(shù)進(jìn)行如下判斷：
- 例 1 不是 二叉搜索樹(shù)。原因：根節(jié)點(diǎn)(值為 6)的左子樹(shù)中有節(jié)點(diǎn)(值為 7)的數(shù)大于根節(jié)點(diǎn)的數(shù)。
- 例 2 不是 二叉搜索樹(shù)。原因：根節(jié)點(diǎn)(值為 6)的右子樹(shù)中有節(jié)點(diǎn)(值為 3)的數(shù)小于根節(jié)點(diǎn)的數(shù)。
- 例 3 不是 二叉搜索樹(shù)。原因：根節(jié)點(diǎn)的左子樹(shù)不是二叉搜索樹(shù)，左子樹(shù)的根節(jié)點(diǎn)的值 5 不僅小于左子節(jié)點(diǎn)的值 7 還大于右子節(jié)點(diǎn)的值 4，并且根節(jié)點(diǎn)的值 6 小于左子樹(shù)中節(jié)點(diǎn)的值 7;根節(jié)點(diǎn)的右子樹(shù)也不是二叉搜索樹(shù)，右子樹(shù)的根節(jié)點(diǎn)的值 8 不僅大于右子節(jié)點(diǎn)的值 3 還小于左子節(jié)點(diǎn)的值 9，并且根節(jié)點(diǎn)的值 6 大于右子樹(shù)中節(jié)點(diǎn)的值 3。
解題思路
根據(jù)二叉搜索樹(shù)的定義，判斷一棵樹(shù)是否是二叉搜索樹(shù)，需要判斷每個(gè)節(jié)點(diǎn)是否符合二叉樹(shù)的性質(zhì)，而且判斷的依據(jù)又是一樣的，因此可采用遞歸法去解答此題。
遞歸
上述提到的判斷的依據(jù)(假設(shè)當(dāng)前節(jié)點(diǎn)存在左右子節(jié)點(diǎn))是指：
- 當(dāng)前節(jié)點(diǎn)的值大于其左子節(jié)點(diǎn)的值;
- 當(dāng)前節(jié)點(diǎn)的值小于其右子節(jié)點(diǎn)的值;
- 如果當(dāng)前節(jié)點(diǎn)存在左右子樹(shù)，則其左右子樹(shù)上的節(jié)點(diǎn)還要滿足：左子樹(shù)上的節(jié)點(diǎn)值小于當(dāng)前節(jié)點(diǎn)的值，右子樹(shù)上的節(jié)點(diǎn)值大于當(dāng)前節(jié)點(diǎn)的值;
根據(jù)以上的思路，可以通過(guò)設(shè)置上下界，來(lái)判斷節(jié)點(diǎn)是否符合二叉搜索樹(shù)的性質(zhì)。
如果存在上下界，則判斷節(jié)點(diǎn)是否在上下界內(nèi)，如不在，則不是二叉搜索樹(shù);否則以該節(jié)點(diǎn)的值作為上界，對(duì)其左子樹(shù)進(jìn)行遞歸判斷，以該節(jié)點(diǎn)的值作為下界，對(duì)其右子樹(shù)進(jìn)行遞歸判斷。
注意
空樹(shù)屬于二叉搜索樹(shù)。
Show me the Code
C
- bool isValidBST_Helper(struct TreeNode* root, double min, double max) {
- /* 特殊判斷 */
- if (root == NULL) {
- return true;
- }
- /* 當(dāng)前節(jié)點(diǎn)不在上下界內(nèi)，不是二叉搜索樹(shù) */
- if (root->val <= min || root->val >= max) {
- return false;
- }
- /* 判斷左右子樹(shù)是否是二叉搜索樹(shù) */
- return isValidBST_Helper(root->left, min, root->val) && isValidBST_Helper(root->right, root->val, max);
- }
- bool isValidBST(struct TreeNode* root) {
- return isValidBST_Helper(root, LONG_MIN, LONG_MAX);
- }
C++
- bool isValidBST_Helper(TreeNode* root, double min, double max) {
- if (root == nullptr) {
- return true;
- }
- if (root->val <= min || root->val >= max) {
- return false;
- }
- return isValidBST_Helper(root->left, min, root->val) && isValidBST_Helper(root->right, root->val, max);
- }
- bool isValidBST(TreeNode* root) {
- return isValidBST_Helper(root, LONG_MIN, LONG_MAX);
- }
Java
- boolean isValidBST_Helper(TreeNode root, double min, double max) {
- if (root == null) {
- return true;
- }
- if (root.val <= min || root.val >= max) {
- return false;
- }
- return isValidBST_Helper(root.left, min, root.val) && isValidBST_Helper(root.right, root.val, max);
- }
- boolean isValidBST(TreeNode root) {
- return isValidBST_Helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
- }
Python3
- def isValidBST(self, root: TreeNode) -> bool:
- def isValidBST_Helper(root, min, right):
- if root is None:
- return True
- if root.val <= min or root.val >= right:
- return False
- return isValidBST_Helper(root.left, min, root.val) and isValidBST_Helper(root.right, root.val, right)
- return isValidBST_Helper(root, -float('inf'), float('inf'))
Golang
- func isValidBST(root *TreeNode) bool {
- return isValidBST_Helper(root, math.MinInt64, math.MaxInt64)
- }
- func isValidBST_Helper(root *TreeNode, min, max int) bool {
- if root == nil {
- return true
- }
- if min >= root.Val || max <= root.Val {
- return false
- }
- return isValidBST_Helper(root.Left, min, root.Val) && isValidBST_Helper(root.Right, root.Val, max)
- }
復(fù)雜度分析
時(shí)間復(fù)雜度：O(n)，其中 n 為二叉樹(shù)節(jié)點(diǎn)的個(gè)數(shù)。
空間復(fù)雜度：O(n)。
深度優(yōu)先搜索
根據(jù)二叉搜索樹(shù)的性質(zhì)，對(duì)其進(jìn)行中序遍歷，得到的數(shù)組一定是升序排列的。因此可以根據(jù)這個(gè)特性，判斷一棵樹(shù)是否是二叉搜索樹(shù)。
如果采用中序遍歷，將二叉樹(shù)的所有節(jié)點(diǎn)的值存放在數(shù)組中，再去判斷該數(shù)組是否是升序的，步驟有點(diǎn)繁瑣。
由于判斷數(shù)組是否是升序排列，只需要判斷數(shù)組的后一個(gè)元素是否大于前一個(gè)元素即可，因此本題可以設(shè)置一個(gè)變量，用于保存中序遍歷前一個(gè)節(jié)點(diǎn)的值，再判斷當(dāng)前節(jié)點(diǎn)的值是否大于該變量保存的值。
如果不大于，則代表該樹(shù)不是二叉搜索樹(shù);否則繼續(xù)遍歷并判斷。
Show me the Code
C++
- long pre = LONG_MIN;
- bool isValidBST(TreeNode* root) {
- if (root == nullptr) {
- return true;
- }
- if (!isValidBST(root->left)) {
- return false;
- }
- if (root->val <= pre) {
- return false;
- }
- pre = root->val;
- return isValidBST(root->right);
- }
Java
- long temp = Long.MIN_VALUE;
- boolean isValidBST(TreeNode root) {
- if (root == null) {
- return true;
- }
- if(!isValidBST(root.left)) {
- return false;
- }
- if (root.val <= temp) {
- return false;
- }
- temp = root.val;
- return isValidBST(root.right);
- }
復(fù)雜度分析
時(shí)間復(fù)雜度：O(n)，其中 n 為二叉樹(shù)節(jié)點(diǎn)的個(gè)數(shù)。
空間復(fù)雜度：O(n)。
