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

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

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

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

python
1- infinity < 3 < 5

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

解答例

python
1        # bfs
2        q = deque()
3        q.append([root, -float("inf"), float("inf")])
4        while q:
5            node, lower, upper = q.popleft()
6            if node.left:
7                if node.val > node.left.val > lower:
8                    q.append([node.left, lower, node.val])
9                else:
10                    return False
11
12            if node.right:
13                if node.val < node.right.val < upper:
14                    q.append([node.right, node.val, upper])
15                else:
16                    return False
17        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

行動規範の内容に同意します

回答2件

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

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

python
1class Solution:
2    def isValidBST(self, root: Optional[TreeNode]) -> bool:
3        def valid(node, left, right):
4            if not node:
5                return True
6            if not (node.val < right and node.val > left):
7                return False
8            return (valid(node.left, left, node.val) and
9                    valid(node.right, node.val, right))
10        return valid(root, float("-inf"), float("inf"))

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

python
1class Solution:
2    def isValidBST(self, root: Optional[TreeNode]) -> bool:
3        q = deque()
4        q.append([root, float("-inf"), float("inf")])
5        while q:
6            node, left, right = q.popleft()
7            if not node:
8                continue
9            if not (node.val < right and node.val > left):
10                return False
11            q.append([node.left, left, node.val])
12            q.append([node.right, node.val, right])
13        return True

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

python
1class Solution:
2    def isValidBST(self, root: Optional[TreeNode]) -> bool:
3        q = deque()
4        q.append([root, float("-inf"), float("inf")])
5        while q:
6            node, left, right = q.popleft()
7            if not (node.val < right and node.val > left):
8                return False
9            if node.left:
10                q.append([node.left, left, node.val])
11            if node.right:
12                q.append([node.right, node.val, right])
13        return True

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

python
1class Solution:
2    def isValidBST(self, root: Optional[TreeNode]) -> bool:
3        q = deque()
4        q.append([root, float("-inf"), float("inf")])
5        while q:
6            node, left, right = q.popleft()
7            if node.left:
8                if not (node.left.val < node.val and node.left.val > left):
9                    return False
10                q.append([node.left, left, node.val])
11            if node.right:
12                if not (node.right.val < right and node.right.val > node.val):
13                    return False
14                q.append([node.right, node.val, right])
15        return True

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

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

投稿2021/10/02 01:01

編集2021/10/02 01:46

actorbug

総合スコア2224

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

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

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

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

投稿2021/07/21 21:41

toshikawa

総合スコア388

sequelanonymous

2021/07/22 05:28 編集

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

行動規範の内容に同意します

あなたの回答