自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

互聯(lián)網(wǎng)經(jīng)典算法之驗(yàn)證二叉搜索樹

作者： Dine
開發(fā) 前端 算法
本文主要介紹遞歸和深度優(yōu)先搜索兩種方法來解答此題，供大家參考，希望對(duì)大家有所幫助。

[[427951]]

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

前言

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

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

驗(yàn)證二叉搜索樹

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

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

節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。

節(jié)點(diǎn)的右子樹只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)。

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

示例 1

示例 2 及提示

二叉搜索樹

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

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

舉例

例 1

例1

例 2

例 3

判斷二叉搜索樹

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

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

解題思路

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

遞歸

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

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

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

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

注意

空樹屬于二叉搜索樹。

Show me the Code

C

  1. bool isValidBST_Helper(struct TreeNode* root, double min, double max) { 
  2.     /* 特殊判斷 */ 
  3.     if (root == NULL) { 
  4.         return true; 
  5.     } 
  6.  
  7.     /* 當(dāng)前節(jié)點(diǎn)不在上下界內(nèi)，不是二叉搜索樹 */ 
  8.     if (root->val <= min || root->val >= max) { 
  9.         return false; 
  10.     } 
  11.  
  12.     /* 判斷左右子樹是否是二叉搜索樹 */ 
  13.     return isValidBST_Helper(root->left, min, root->val) && isValidBST_Helper(root->right, root->val, max); 
  14. } 
  15.  
  16. bool isValidBST(struct TreeNode* root) { 
  17.     return isValidBST_Helper(root, LONG_MIN, LONG_MAX); 
  18. } 

C++

  1. bool isValidBST_Helper(TreeNode* root, double min, double max) { 
  2.     if (root == nullptr) { 
  3.         return true; 
  4.     } 
  5.  
  6.     if (root->val <= min || root->val >= max) { 
  7.         return false; 
  8.     } 
  9.  
  10.     return isValidBST_Helper(root->left, min, root->val) && isValidBST_Helper(root->right, root->val, max); 
  11. } 
  12.  
  13. bool isValidBST(TreeNode* root) { 
  14.     return isValidBST_Helper(root, LONG_MIN, LONG_MAX); 
  15. } 

Java

  1. boolean isValidBST_Helper(TreeNode root, double min, double max) { 
  2.     if (root == null) { 
  3.         return true; 
  4.     } 
  5.  
  6.     if (root.val <= min || root.val >= max) { 
  7.         return false; 
  8.     } 
  9.  
  10.     return isValidBST_Helper(root.left, min, root.val) && isValidBST_Helper(root.right, root.val, max); 
  11. } 
  12.  
  13. boolean isValidBST(TreeNode root) { 
  14.     return isValidBST_Helper(root, Long.MIN_VALUE, Long.MAX_VALUE); 
  15. } 

Python3

  1. def isValidBST(self, root: TreeNode) -> bool: 
  2.     def isValidBST_Helper(root, min, right): 
  3.         if root is None: 
  4.             return True 
  5.          
  6.         if root.val <= min or root.val >= right: 
  7.             return False 
  8.  
  9.         return isValidBST_Helper(root.left, min, root.val) and isValidBST_Helper(root.right, root.val, right) 
  10.  
  11.     return isValidBST_Helper(root, -float('inf'), float('inf'))  

Golang

  1. func isValidBST(root *TreeNode) bool { 
  2.   return isValidBST_Helper(root, math.MinInt64, math.MaxInt64) 
  3. } 
  4.  
  5. func isValidBST_Helper(root *TreeNode, min, max int) bool { 
  6.   if root == nil { 
  7.     return true 
  8.   } 
  9.  
  10.   if min >= root.Val || max <= root.Val { 
  11.     return false 
  12.   } 
  13.  
  14.   return isValidBST_Helper(root.Left, min, root.Val) && isValidBST_Helper(root.Right, root.Val, max) 
  15. } 

復(fù)雜度分析

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

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

深度優(yōu)先搜索

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

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

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

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

Show me the Code

C++

  1. long pre = LONG_MIN; 
  2. bool isValidBST(TreeNode* root) { 
  3.     if (root == nullptr) { 
  4.         return true; 
  5.     } 
  6.  
  7.     if (!isValidBST(root->left)) { 
  8.         return false; 
  9.     } 
  10.  
  11.     if (root->val <= pre) { 
  12.         return false; 
  13.     } 
  14.  
  15.     pre = root->val;  
  16.     return isValidBST(root->right);       
  17. } 

Java

  1. long temp = Long.MIN_VALUE; 
  2. boolean isValidBST(TreeNode root) { 
  3.     if (root == null) { 
  4.         return true; 
  5.     } 
  6.  
  7.     if(!isValidBST(root.left)) { 
  8.         return false; 
  9.     } 
  10.  
  11.     if (root.val <= temp) { 
  12.         return false; 
  13.     }  
  14.  
  15.     temp = root.val; 
  16.     return isValidBST(root.right);         
  17. } 

復(fù)雜度分析

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

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

 

責(zé)任編輯：武曉燕 來源： 程序員小熊
遞歸二叉搜索樹
相關(guān)推薦

2022-01-11 10:01:25

二叉搜索樹數(shù)量

2022-12-26 00:51:33

雙向鏈表二叉搜索樹

2021-08-31 11:35:24

二叉搜索樹迭代法公共祖先

2021-12-07 06:55:17

二叉搜索樹鏈表

2021-09-29 10:19:00

算法平衡二叉樹

2020-09-23 18:25:40

算法二叉樹多叉樹

2013-07-15 16:35:55

二叉樹迭代器

2020-11-02 09:15:47

算法與數(shù)據(jù)結(jié)構(gòu)

2023-07-31 08:01:13

二叉搜索測(cè)試

2021-09-03 08:58:00

二叉搜索樹節(jié)點(diǎn)

2021-09-02 11:31:28

二叉搜索樹迭代法公共祖先

2023-05-04 07:30:28

二叉搜索樹BST

2020-04-27 07:05:58

二叉樹左子樹右子樹

2021-03-22 08:23:29

LeetCode二叉樹節(jié)點(diǎn)

2021-09-07 11:01:41

二叉搜索樹序數(shù)組

2021-08-26 11:31:11

二叉樹數(shù)據(jù)結(jié)構(gòu)算法

2024-01-17 07:36:50

二叉搜索聯(lián)系簿

2021-04-28 20:12:27

數(shù)據(jù)結(jié)構(gòu)創(chuàng)建

2023-02-13 08:02:08

哈希函數(shù)哈希表搜索樹

2021-09-15 07:56:32

二叉樹層次遍歷
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)