98. Validate Binary Search Treeのbfsアプローチの場合のinfinityの扱い

Question

タイトルに有る通りの問題をbfsを使用した解答例のコードリーディングをしています。
なぜ、-float("inf"), float("inf") をしているのか、もしくは-float("inf"), float("inf")をｄのように利用しているのか、が理解できません。

この動画の解説によると、親ノードはなんでもいい、といってるのでininityを利用してるみたいですが、何でもいい理由がわかりません。

たとえば、下記のような解釈がでてきますが、なぜ、どうやってこういう解釈にたどりついたのかが理解できません。

- infinity < 3 < 5 

どなたか、噛み砕いてご説明できる方いらっしゃいますでしょうか？

解答例

        # bfs
        q = deque()
        q.append([root, -float("inf"), float("inf")])
        while q:
            node, lower, upper = q.popleft()
            if node.left:
                if node.val > node.left.val > lower:
                    q.append([node.left, lower, node.val])
                else:
                    return False

            if node.right:
                if node.val < node.right.val < upper:
                    q.append([node.right, node.val, upper])
                else:
                    return False
        return True

問題文

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

引用元：98. Validate Binary Search Tree

Answer 1

infが分からないという質問からif node.val > node.left.val > lower:が分からないという質問に変わってしまっているようなので、そちらの説明のために動画のコードから解答例のコードに変形してみましょうか。

動画のコードは以下のようになっていました。

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def valid(node, left, right):
            if not node:
                return True
            if not (node.val < right and node.val > left):
                return False
            return (valid(node.left, left, node.val) and
                    valid(node.right, node.val, right))
        return valid(root, float("-inf"), float("inf"))

この再帰のコードは、すべてのノードについてvalidが成立するか確認しているので、BFSに書き換えられます。BFSに書き換えるには、ノードを順番にキューに登録していけばよいですが、今回はノードごとにleft, rightの値が変わるので、そちらもいっしょにキューに登録する必要があります。

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        q = deque()
        q.append([root, float("-inf"), float("inf")])
        while q:
            node, left, right = q.popleft()
            if not node:
                continue
            if not (node.val < right and node.val > left):
                return False
            q.append([node.left, left, node.val])
            q.append([node.right, node.val, right])
        return True

さて、if not node: continueの部分に着目すると、nodeがNoneの場合は何もしないで読み飛ばしていることが分かります。つまり、nodeがNoneのノードをキューに登録するのは無駄です。事前に判定して登録しないようにしましょう。ただし、rootは問題の条件によりNoneでないことが確定しているので判定しません。

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        q = deque()
        q.append([root, float("-inf"), float("inf")])
        while q:
            node, left, right = q.popleft()
            if not (node.val < right and node.val > left):
                return False
            if node.left:
                q.append([node.left, left, node.val])
            if node.right:
                q.append([node.right, node.val, right])
        return True

次にif not (node.val < right and node.val > left): return Falseに着目すると、この条件を満たす場合はそのままFalseを返していることが分かります。つまり、この条件を満たすノードは、キューに登録しないでいきなりFalseを返してしまってよいことになります。事前に判定するようにしましょう。ただし、rootはこの条件を満たすことはないので判定しません。

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        q = deque()
        q.append([root, float("-inf"), float("inf")])
        while q:
            node, left, right = q.popleft()
            if node.left:
                if not (node.left.val < node.val and node.left.val > left):
                    return False
                q.append([node.left, left, node.val])
            if node.right:
                if not (node.right.val < right and node.right.val > node.val):
                    return False
                q.append([node.right, node.val, right])
        return True

あとは、変数名の付け替えと簡単な変形で、解答例の形にもちこめるでしょう。

最後の変形の過程でわかると思いますが、if node.val > node.left.val > lower:という条件文のそもそもの目的は、node.leftが条件を満たすかどうか事前に判断することにあります。そう考えれば、node.left.valが中央にあるのも納得できるのではないでしょうか。

Answer 2

この問題が __validate__つまり正しくBTSになっているか確認する必要があります。

入力値の範囲が-2^31 <= Node.val <= 2^31 - 1と大きいのでfloat('inf')を使用しているのではないでしょうか。

nodeがなんでもいいといっているのは、上記の範囲の値という意味だと思います。

また、- infinity < 3 < 5 は正しくTrueを返すので、使っていると思います。

Comments

[sequelanonymous]

ご回答ありがとうございます！
私もそこまでは理解していて、BSTの場合、left > node > rightっていう順番になるはずなので、
node.valが真ん中にくるのであれば、理解できますが、下記のような条件文を記載している理由がわかりません。
if node.val > node.left.val > lower: