#7 Trees: Is This a Binary Search Tree?
データ構造が二分探索木になっているかどうかをチェックする問題。
- The value of every node in a node’s left subtree is less than the data value of that node.
- The value of every node in a node’s right subtree is greater than the data value of that node.
つまり、与えられたデータ構造が二分木探索木(左の子の値 < 親の値 < 右の子の値)となっているかどうかをチェックする。 チェックして、データ構造が二分探索木になっていれば、trueを、それ以外はfalseを返せばよい。
solution
python3での解
def check(root, min, max): if root == None: return True if root.data <= min or max <= root.data: return False return check(root.left, min, root.data) and check(root.right, root.data, max) def checkBST(root): return check(root, float('-inf'), float('inf'))
Binary Tree とは
二分木（binary tree; 二進木、バイナリツリー）は、データ構造の1つである。根付き木構造の中で、あるノード（節点 node）が持つ子の数が高々2であるものをいう。典型的には2つの子はそれぞれ「左」「右」と呼ばれる。 たとえば、二分探索や二分ヒープを実装するために使われる。
Binary Search Tree とは
二分探索木（にぶんたんさくぎ、英: binary search tree）は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。
