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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 难道不是 inorder tree transversal?
|
|