[[427951]]

本文轉載自微信公眾號「程序員小熊」，作者Dine 。轉載本文請聯系程序員小熊公眾號。

前言

大家好，我是來自于華為的程序員小熊。今天給大家帶來一道與二叉樹相關的面試高頻題，這道題在半年內被谷歌、字節、微軟和亞馬遜等大廠作為面試題，即力扣上的第98題-驗證二叉搜索樹。

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

驗證二叉搜索樹

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

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

節點的左子樹只包含小于當前節點的數。

節點的右子樹只包含大于當前節點的數。

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

示例 1

示例 2 及提示

二叉搜索樹

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

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

舉例

例 1

例1

例 2

例 3

判斷二叉搜索樹

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

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

解題思路

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

遞歸

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

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

根據以上的思路，可以通過設置上下界，來判斷節點是否符合二叉搜索樹的性質。

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

注意

空樹屬于二叉搜索樹。

Show me the Code

C

bool isValidBST_Helper(struct 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); 
} 
 
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) 
} 

復雜度分析

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

空間復雜度：O(n)。

深度優先搜索

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

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

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

如果不大于，則代表該樹不是二叉搜索樹;否則繼續遍歷并判斷。

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);         
} 

復雜度分析

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

空間復雜度：O(n)。