LeetCode 98二叉探索ツリーValidate Binary Search Tree Pythonの検証

二叉樹に関する問題メモ、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の検証
LeetCodeCN第98題リンク
第1の方法:中序は二叉木を遍歴して配列に格納し、直接昇順ソートして重量を除去した元の二叉木と比較する.

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)

第2の方法:中順遍歴は、前のノードの値が現在のノードの値より小さいかどうかを比較するだけで、保存する必要はありません.

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)

第3の方法:各ノードの左の子供の値が親ノードの値より小さいかどうか、および右の子供の値が親ノードの値より大きいかどうかを再帰的に検証する.

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)

次の問題:236.二叉木の最近の公共の祖先Lowest Common Ancestor of a Binary Tree