有关二叉树的做题笔记，Python实现
二叉树的定义
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
98. 验证二叉搜索树 Validate Binary Search Tree
第一种方法：中序遍历二叉树存入数组，与直接升序排序去重后的原二叉树对比
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
inorder = self.inorder(root)
return inorder == list(sorted(set(inorder)))
def inorder(self, root) -> list:
if root is None:
return []
return self.inorder(root.left) + [root.val] + self.inorder(root.right)
第二种方法：中序遍历只用比较前一节点的值是否小于当前节点的值即可，不用储存
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
self.prev = None
return self.helper(root)
def helper(self, root):
if root is None:
return True
if not self.helper(root.left):
return False
if self.prev and self.prev.val >= root.val:
return False
self.prev = root
return self.helper(root.right)
第三种方法：递归验证每个节点左孩子的值是否小于父亲节点的值以及右孩子的值是否大于父亲节点的值
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
mini, maxi = float('-inf'), float('inf')
return self.isValid(root, mini, maxi)
def isValid(self, root: TreeNode, mini: int, maxi: int) -> bool:
if root is None:
return True
if mini >= root.val or maxi <= root.val:
return False
return self.isValid(root.left, mini, root.val) and self.isValid(root.right, root.val, maxi)
