質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

ループ

ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

2回答

925閲覧

Binary Search Treeのvalidationコードをstackを利用するも微妙なエッジケースのカバーがなかなかできない。

sequelanonymous

総合スコア123

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

ループ

ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2021/09/25 08:46

下記のコードで正常系BSTの確認をするコードは実装できましたが、[0,-1]のような片方しかないTree構造の場合のエッジケースがカバーできません。
そのエッジケースに特化したコードを実装しようとすると、こんごは正常系BSTのvalidateが通らなくなるコードができてしまいます。

下記Stackで実装されたコードをちょっとこう変えるだけでエッジケースのカバーができるなどお気づきの点ありましたらご教示いただけませんしょうか?

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.

98. Validate Binary Search Tree

Stackで実装したBSTのvalidationコード

python

1# Definition for a binary tree node. 2# class TreeNode: 3# def __init__(self, val=0, left=None, right=None): 4# self.val = val 5# self.left = left 6# self.right = right 7class Solution: 8 def isValidBST(self, root: Optional[TreeNode]) -> bool: 9 if not root: 10 return False 11 12 if not root.left and not root.right: 13 return True 14 15 stack = [[root, root.val]] 16 left_val, right_val = -float("inf"), -float("inf") 17 while stack: 18 curr, val = stack.pop() 19 20 if curr.left: 21 stack.append([curr.left, curr.left.val]) 22 left_val = curr.left.val 23 24 if curr.right: 25 stack.append([curr.right, curr.right.val]) 26 right_val = curr.right.val 27 28 if left_val < val < right_val: 29 return True 30 else: 31 return False 32 33 return True 34

成功する。

Your input [2,1,3] Output true Expected true

下記のインプットの場合のエッジケースをどうすればカバーできるか。

Input: [0,-1] Output: false Expected: true

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

提示されたコードを見ていると、以下のような勘違いをしているのではないかと心配になってしまいます。

すべてのノードについて、左の子ノードの値 < そのノードの値 < 右の子ノードの値 という条件が満たされれば、正常なBSTである。

念のため、反例を出しておきます。

リンク先の例2で、「4」と「5」を入れ替えた木を考えます。
入力としては、root = [4,1,5,null,null,3,6]となるでしょうか。

すべてのノードについて、上記の判断基準を満たすか確認してみます。

まず「4」のノードですが、左が「1」で右が「5」なので 1 < 4 < 5 で条件を満たします。
次に「5」のノードですが、左が「3」で右が「6」なので 3 < 5 < 6 で条件を満たします。
すべてのノードで条件を満たすので、この基準に従うなら、正常なBSTであると判定されます。

しかし、「4」の右のサブツリー内に「3」が存在するので、以下の条件が満たされていないことが分かります。

  • The right subtree of a node contains only nodes with keys greater than the node's key.

つまり、この木は正常なBSTではありません。
よって、最初に示した判断基準では、正常なBSTの判定ができないということが分かります。

投稿2021/09/30 13:45

編集2021/09/30 20:40
actorbug

総合スコア2212

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

エッジケースでも何でもないです。
うまくいってるほうがたまたまです。

LeetCodeだと自分でテストケースを試せるのでいろいろ試してみてください。いくらでも間違った結果が出ます。

投稿2021/09/25 10:04

編集2021/09/25 10:17
yudedako67

総合スコア2047

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問