偷偷摘套内射激情视频,久久精品99国产国产精,中文字幕无线乱码人妻,中文在线中文a,性爽19p

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

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

[[427951]]

本文轉(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))是指：

  1. 當(dāng)前節(jié)點(diǎn)的值大于其左子節(jié)點(diǎn)的值;
  2. 當(dāng)前節(jié)點(diǎn)的值小于其右子節(jié)點(diǎn)的值;
  3. 如果當(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

  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)，不是二叉搜索樹(shù) */ 
  8.     if (root->val <= min || root->val >= max) { 
  9.         return false; 
  10.     } 
  11.  
  12.     /* 判斷左右子樹(shù)是否是二叉搜索樹(shù) */ 
  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 為二叉樹(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++

  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 為二叉樹(shù)節(jié)點(diǎn)的個(gè)數(shù)。

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

 

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

2022-01-11 10:01:25

二叉搜索樹(shù)數(shù)量

2022-12-26 00:51:33

雙向鏈表二叉搜索樹(shù)

2021-08-31 11:35:24

二叉搜索樹(shù)迭代法公共祖先

2021-12-07 06:55:17

二叉搜索樹(shù)鏈表

2013-07-15 16:35:55

二叉樹(shù)迭代器

2021-09-29 10:19:00

算法平衡二叉樹(shù)

2020-09-23 18:25:40

算法二叉樹(shù)多叉樹(shù)

2020-11-02 09:15:47

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

2023-07-31 08:01:13

二叉搜索測(cè)試

2021-09-03 08:58:00

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

2021-09-02 11:31:28

二叉搜索樹(shù)迭代法公共祖先

2020-04-27 07:05:58

二叉樹(shù)左子樹(shù)右子樹(shù)

2023-05-04 07:30:28

二叉搜索樹(shù)BST

2021-03-22 08:23:29

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

2023-02-13 08:02:08

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

2024-01-17 07:36:50

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

2021-08-26 11:31:11

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

2021-09-07 11:01:41

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

2021-09-15 07:56:32

二叉樹(shù)層次遍歷

2021-04-28 20:12:27

數(shù)據(jù)結(jié)構(gòu)創(chuàng)建
點(diǎn)贊
收藏

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