LeetCode初級演算法--樹02：驗證二叉搜索樹
搜索微信公眾號:'AI-ming3526'或者'計算機視覺這件小事' 獲取更多演算法、機器學習干貨
csdn：https://blog.csdn.net/baidu_31657889/
csdn：https://blog.csdn.net/abcgkj/
github：https://github.com/aimi-cn/AILearners
一、引子
這是由LeetCode官方推出的的經典面試題目清單~
這個模塊對應的是探索的初級演算法~旨在幫助入門演算法，我們第一遍刷的是leetcode推薦的題目，
查看完整的劍指Offer演算法題決議請點擊github鏈接：
github地址
二、題目
給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹，
假設一個二叉搜索樹具有如下特征：
- 節點的左子樹只包含小于當前節點的數，
- 節點的右子樹只包含大于當前節點的數，
- 所有左子樹和右子樹自身必須也是二叉搜索樹，
示例1:
輸入:
2
/ \
1 3
輸出: true
示例2:
輸入:
5
/ \
1 4
/ \
3 6
輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]，
根節點的值為 5 ，但是其右子節點值為 4 ，
1、思路
- 為了驗證一棵樹是否是BST，我們可以一個節點一個節點的查看，
- 每一個節點都有一個最大值和最小值的范圍，
- 哎？為什么一個節點有一個最大值和最小值的范圍？
- 我們舉個例子，
5
/ \
1 8
/ \
3 10
在上述的樹當中，1比5小，8比5大，第一層OK
再第二層，3比8小，10比8大，OK....OK嗎？
不OK！因為3在5的右子樹，應當比5大，
所以不可以直觀地認為一個節點只要比父節點大或者小就可以了，它實際上是由大小范圍的，
對于這個3,它應該的范圍就是(5,8)，
最大值和最小值怎么更新呢？
很簡單，如果要檢查的節點在這個節點的左邊，那么最大值就是這個節點的值，最小值就是上一輪檢查當中的最小值，
反之亦然，
2、編程實作
python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 初始化root的時候，它沒有最大最小的限制
def isValidBST(self, root: TreeNode, low = float('-inf'), high = float('inf')) -> bool:
# 當這個節點不存在的時候，就回傳True，就代表父節點沒有（左或右）孩子
if not root:return True
# 判斷當前節點是否大于最小值和小于最大值
if not low<root.val<high:return False
# 遞回檢查左右孩子，兩個都為True才可以回傳True
return self.isValidBST(root.left,low,root.val) and self.isValidBST(root.right,root.val,high)
AIMI-CN AI學習交流群【1015286623】 獲取更多AI資料
分享技術，樂享生活：我們的公眾號計算機視覺這件小事每周推送“AI”系列資訊類文章，歡迎您的關注！
本文由博客一文多發平臺 OpenWrite 發布！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/67696.html
標籤：其他