98. 驗證二叉搜索樹
題目來源：https://leetcode-cn.com/problems/validate-binary-search-tree
題目
給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹，
假設一個二叉搜索樹具有如下特征：
節點的左子樹只包含小于當前節點的數，
節點的右子樹只包含大于當前節點的數，
所有左子樹和右子樹自身必須也是二叉搜索樹，
示例 1:
輸入:
2
/ \
1 3
輸出: true
示例 2:
輸入:
5
/ \
1 4
/ \
3 6
輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]，
根節點的值為 5 ，但是其右子節點值為 4 ，
解題思路
思路：中序遍歷
根據題意，二叉搜索樹有如下的性質：
- 當二叉樹的左子樹不是空時，左子樹上的所有節點值都小于它根節點的值
- 當二叉樹的右子樹不為空時，右子樹上所有節點值都大于根節點的值
- 左右子樹同樣也是二叉搜索樹
從上面的性質可以看出，二叉搜索樹【中序遍歷】得到的值一定是升序的，那么就這個特性，我們在中序遍歷的時候就可以考慮檢查當前節點的值是否大于前一個中序遍歷到的節點的值，如果都大于則說明這個序列是升序的，那么就與前面就性質所得出的結論是吻合的，那么整棵樹就是二叉搜索樹，
關于【中序遍歷】，它是二叉樹遍歷的一種，在二叉樹中，中序遍歷首先遍歷左子樹，然后訪問根節點，最后遍歷右子樹，
具體實作代碼如下，
代碼實作
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
stack = []
# -inf 表負無窮
inorder = float('-inf')
while root or stack:
# 將左點壓入堆疊中
while root:
stack.append(root)
root = root.left
# 進行中序遍歷
root = stack.pop()
# 如果當前節點的值小于前面中序遍歷的值時，就不是二叉搜索樹
while root.val <= inorder:
return False
# 更新中序遍歷的值
inorder = root.val
root = root.right
return True
實作結果
以上就是根據二叉搜索樹的性質，用堆疊實作中序遍歷的思路，進而解決《98. 驗證二叉搜索樹》問題的主要內容，
歡迎關注微信公眾號《書所集錄》
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/150268.html
標籤：Python