[[427951]]

本文轉(zhuǎn)載自微信公眾號「程序員小熊」，作者Dine 。轉(zhuǎn)載本文請聯(lián)系程序員小熊公眾號。

前言

大家好，我是來自于華為的程序員小熊。今天給大家?guī)硪坏琅c二叉樹相關(guān)的面試高頻題，這道題在半年內(nèi)被谷歌、字節(jié)、微軟和亞馬遜等大廠作為面試題，即力扣上的第98題-驗證二叉搜索樹。

本文主要介紹遞歸和深度優(yōu)先搜索兩種方法來解答此題，供大家參考，希望對大家有所幫助。

驗證二叉搜索樹

給你一個二叉樹的根節(jié)點 root ，判斷其是否是一個有效的二叉搜索樹。

有效二叉搜索樹定義如下：

節(jié)點的左子樹只包含小于當前節(jié)點的數(shù)。

節(jié)點的右子樹只包含大于當前節(jié)點的數(shù)。

所有左子樹和右子樹自身必須也是二叉搜索樹。

示例 1

示例 2 及提示

二叉搜索樹

題目已提示有效二叉搜索樹的定義如下：

• 節(jié)點的左子樹只包含小于當前節(jié)點的數(shù)。
• 節(jié)點的右子樹只包含大于當前節(jié)點的數(shù)。
• 所有左子樹和右子樹自身必須也是二叉搜索樹。

舉例

例 1

例1

例 2

例 3

判斷二叉搜索樹

針對上面的舉例，根據(jù)二叉搜索樹的判斷方法，對上面的例子是否是二叉搜索樹進行如下判斷：

• 例 1 不是 二叉搜索樹。原因：根節(jié)點(值為 6)的左子樹中有節(jié)點(值為 7)的數(shù)大于根節(jié)點的數(shù)。
• 例 2 不是 二叉搜索樹。原因：根節(jié)點(值為 6)的右子樹中有節(jié)點(值為 3)的數(shù)小于根節(jié)點的數(shù)。
• 例 3 不是 二叉搜索樹。原因：根節(jié)點的左子樹不是二叉搜索樹，左子樹的根節(jié)點的值 5 不僅小于左子節(jié)點的值 7 還大于右子節(jié)點的值 4，并且根節(jié)點的值 6 小于左子樹中節(jié)點的值 7;根節(jié)點的右子樹也不是二叉搜索樹，右子樹的根節(jié)點的值 8 不僅大于右子節(jié)點的值 3 還小于左子節(jié)點的值 9，并且根節(jié)點的值 6 大于右子樹中節(jié)點的值 3。

解題思路

根據(jù)二叉搜索樹的定義，判斷一棵樹是否是二叉搜索樹，需要判斷每個節(jié)點是否符合二叉樹的性質(zhì)，而且判斷的依據(jù)又是一樣的，因此可采用遞歸法去解答此題。

遞歸

上述提到的判斷的依據(jù)(假設(shè)當前節(jié)點存在左右子節(jié)點)是指：

1. 當前節(jié)點的值大于其左子節(jié)點的值;
2. 當前節(jié)點的值小于其右子節(jié)點的值;
3. 如果當前節(jié)點存在左右子樹，則其左右子樹上的節(jié)點還要滿足：左子樹上的節(jié)點值小于當前節(jié)點的值，右子樹上的節(jié)點值大于當前節(jié)點的值;

根據(jù)以上的思路，可以通過設(shè)置上下界，來判斷節(jié)點是否符合二叉搜索樹的性質(zhì)。

如果存在上下界，則判斷節(jié)點是否在上下界內(nèi)，如不在，則不是二叉搜索樹;否則以該節(jié)點的值作為上界，對其左子樹進行遞歸判斷，以該節(jié)點的值作為下界，對其右子樹進行遞歸判斷。

注意

空樹屬于二叉搜索樹。

Show me the Code

C

bool isValidBST_Helper(struct TreeNode* root, double min, double max) { 
    /* 特殊判斷 */ 
    if (root == NULL) { 
        return true; 
    } 
 
    /* 當前節(jié)點不在上下界內(nèi)，不是二叉搜索樹 */ 
    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(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ù)雜度分析

時間復(fù)雜度：O(n)，其中 n 為二叉樹節(jié)點的個數(shù)。

空間復(fù)雜度：O(n)。

深度優(yōu)先搜索

根據(jù)二叉搜索樹的性質(zhì)，對其進行中序遍歷，得到的數(shù)組一定是升序排列的。因此可以根據(jù)這個特性，判斷一棵樹是否是二叉搜索樹。

如果采用中序遍歷，將二叉樹的所有節(jié)點的值存放在數(shù)組中，再去判斷該數(shù)組是否是升序的，步驟有點繁瑣。

由于判斷數(shù)組是否是升序排列，只需要判斷數(shù)組的后一個元素是否大于前一個元素即可，因此本題可以設(shè)置一個變量，用于保存中序遍歷前一個節(jié)點的值，再判斷當前節(jié)點的值是否大于該變量保存的值。

如果不大于，則代表該樹不是二叉搜索樹;否則繼續(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ù)雜度分析

時間復(fù)雜度：O(n)，其中 n 為二叉樹節(jié)點的個數(shù)。

空間復(fù)雜度：O(n)。