LeetCode 98—Validate Binary Search Tree(C++Java Python)
2666 ワード
タイトル:http://oj.leetcode.com/problems/validate-binary-search-tree/
Given a binary tree,determine if it is a valid binary search tree(BST)
Asume a 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. タイトル翻訳:
二叉樹を与えて、有効な二叉ルックアップツリー(BST)かどうかを判定します。一つのBSTの定義は、一つのノードの左のサブツリーが、ノード値より小さいノードだけを含むと仮定する。1つのノードの右サブツリーは、ノード値より大きい値のノードのみを含む。左のサブツリーと右のサブツリーも、必ずフォークルックアップツリーでなければなりません。分析:
再帰的に実現する。ノードが空の場合はtrueに戻ります。
C++実現:
読んでくれてありがとうございます。
Given a binary tree,determine if it is a valid binary search tree(BST)
Asume a BST is defined as follows:
二叉樹を与えて、有効な二叉ルックアップツリー(BST)かどうかを判定します。一つのBSTの定義は、一つのノードの左のサブツリーが、ノード値より小さいノードだけを含むと仮定する。1つのノードの右サブツリーは、ノード値より大きい値のノードのみを含む。左のサブツリーと右のサブツリーも、必ずフォークルックアップツリーでなければなりません。分析:
再帰的に実現する。ノードが空の場合はtrueに戻ります。
C++実現:
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode *root) {
return isValidBST(root, INT_MIN, INT_MAX);
}
bool isValidBST(TreeNode *root, int min, int max)
{
if(root == NULL)
{
return true;
}
return root->val > min && root->val < max
&& isValidBST(root->left, min, root->val)
&& isValidBST(root->right, root->val, max);
}
};
Java実装:/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public boolean isValidBST(TreeNode root, int min, int max) {
if (root == null) {
return true;
}
return root.val > min && root.val < max
&& isValidBST(root.left, min, root.val)
&& isValidBST(root.right, root.val, max);
}
}
Python実現:(pythonは重負荷をサポートしていません)# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return a boolean
def isValidBST(self, root):
return self.isValidBSTImpl(root, -2**31, 2**31 - 1)
def isValidBSTImpl(self, root, min, max):
if root == None:
return True
return root.val > min and root.val < max \
and self.isValidBSTImpl(root.left, min, root.val) \
and self.isValidBSTImpl(root.right, root.val, max)
読んでくれてありがとうございます。