c***C
发帖数: 139 | 1 Given a binary search tree, find the total number of integers
in between min and max.
30
/
25 40
/
15 28 50
i.e.: count_nodes(..., 20, 50) --> 5
class BST(object):
"""
A Binary search tree.
"""
def __init__(self, value, left, right):
self.value = value
self.left = left
self.right = right
def count_nodes(self, min_, max_):
def count_nodes_(self, count):
if self is not None:
# need to traverse both the left child and the right child
if min_ <= self.value <= max_:
count += 1
count = count_nodes_(self.left, count)
count = count_nodes_(self.right, count)
# only need to traverse the right child
elif self.value < min_:
count = count_nodes_(self.right, count)
# only need to traverse the left child
else:
count = count_nodes_(self.left, count)
return count
return count_nodes_(self, 0)
root = BST(35,
BST(25,
BST(18,
BST(7, None, None),
BST(20, None, None)),
BST(32,
None,
BST(34, None, None))),
BST(43,
BST(40, None, None),
BST(60,
BST(50, None, None),
BST(64, None, None))))
print(root.count_nodes(20, 50)) | m******n
发帖数: 187 | 2 谢谢。
【在 c***C 的大作中提到】
: Given a binary search tree, find the total number of integers
: in between min and max.
: 30
: /
: 25 40
: /
: 15 28 50
: i.e.: count_nodes(..., 20, 50) --> 5
: class BST(object):
: """
| D**********d
发帖数: 849 | 3 Solution: Tree recursion.
// root != NULL.
int GetNodeNumberBetween(node*root,int min, int max){
int num = root->val >= min && root->val <= max;
if(root->left && root->val >= min) num += GetNodeNumberBetween(root-Left,
min, max);
if(root->right && root->val <= max) num += GetNodeNumberBetween(root-Left,
min,
max);
return num;
} | s********u
发帖数: 1109 | 4 有笔误，第二个if语句后面是root->right 呵呵
Left,
【在 D**********d 的大作中提到】
: Solution: Tree recursion.
: // root != NULL.
: int GetNodeNumberBetween(node*root,int min, int max){
: int num = root->val >= min && root->val <= max;
: if(root->left && root->val >= min) num += GetNodeNumberBetween(root-Left,
: min, max);
: if(root->right && root->val <= max) num += GetNodeNumberBetween(root-Left,
: min,
: max);
: return num;
| c********p
发帖数: 1969 | | s****s
发帖数: 40 | 6 难道不是 inorder tree transversal？ | s*w
发帖数: 729 | 7 就是每个 node 加个 rank 最简单啊, 不知道你这个题目里面的 bst 是自己设计还
是给定的?
【在 c***C 的大作中提到】
: Given a binary search tree, find the total number of integers
: in between min and max.
: 30
: /
: 25 40
: /
: 15 28 50
: i.e.: count_nodes(..., 20, 50) --> 5
: class BST(object):
: """
| s*w
发帖数: 729 | 8 这个很牛叉
Left,
【在 D**********d 的大作中提到】
: Solution: Tree recursion.
: // root != NULL.
: int GetNodeNumberBetween(node*root,int min, int max){
: int num = root->val >= min && root->val <= max;
: if(root->left && root->val >= min) num += GetNodeNumberBetween(root-Left,
: min, max);
: if(root->right && root->val <= max) num += GetNodeNumberBetween(root-Left,
: min,
: max);
: return num;
| s********u
发帖数: 1109 | 9 是3楼写的那个方法，是preorder。你是不是理解成，min是节点代表的值的最小值？，
我一开始也这么以为，后来一看不对。。min和max是给定的，否则例子不对。
【在 s****s 的大作中提到】
: 难道不是 inorder tree transversal？
|
|
