z*******o
发帖数: 4773 | 1 一个BST, 给你一个区间, 返回结点值全部在区间内的子树的结点个数.
比如:
2
1 3
区间 [1,2], 只有子树1,
返回结点个数1 . | h*********2
发帖数: 444 | | H******7
发帖数: 1728 | 3 随便写一個 见笑了
TreeNode findRange(TreeNode root, int l, int r){
if(root == null) return root;
if(root.val < l){
return findRange(root.left, l, r);
} else if(root.val > r){
return findRange(root.right, l, r);
} else {
if(root.val == l){
if(root.left == null){
return root;
} else {
return findRange(root.right, l, r);
}
} else if(root.val == r){
if(root.right == null){
return root;
} else {
return findRange(root.left, l, r);
}
}
}
return root;
} | H******7
发帖数: 1728 | | P**********0
发帖数: 412 | 5 上面的解法，是不是return的值不对，现在要求的是子树的结点个数 | j**********0
发帖数: 20 | 6 public static class BinaryNode{
BinaryNode leftChild;
BinaryNode rightChild;
int val;
public BinaryNode(int val) {
super();
this.val = val;
}
}
public int find(BinaryNode node, int from, int to){
int[] inRangeSubTree=new int[1];
find(node, from, to, inRangeSubTree);
return inRangeSubTree[0];
}
public boolean find(BinaryNode node, int from, int to, int[]
inRangeSubTree){
if (node==null){
return true;
}
boolean allInRangeLeft=false;
if (node.val>=from){
allInRangeLeft=find(node.leftChild, from, to,inRangeSubTree);
}
boolean allInRangeRight=false;
if (node.val<=to){
allInRangeRight=find(node.rightChild, from, to, inRangeSubTree);
}
if (allInRangeLeft && allInRangeRight && (node.val>=from&& node.val<
=to)){
inRangeSubTree[0]++;
return true;
}
return false;
} | n******n
发帖数: 12088 | 7 什么叫子树的节点数目？
【在 z*******o 的大作中提到】
: 一个BST, 给你一个区间, 返回结点值全部在区间内的子树的结点个数.
: 比如:
: 2
: 1 3
: 区间 [1,2], 只有子树1,
: 返回结点个数1 .
| S******n
发帖数: 489 | 8 应该是能找到多少颗子树，这些子树内的节点的值都在给定范围内。 | h**p
发帖数: 211 | 9 感觉不会有lgN的解法，除非对树的形状有规定，比如perfect bst
普通的bst怎么用lgN的方法得到某一个sub tree的里面的节点个数？更别提规定值得大
小了
【在 z*******o 的大作中提到】
: 一个BST, 给你一个区间, 返回结点值全部在区间内的子树的结点个数.
: 比如:
: 2
: 1 3
: 区间 [1,2], 只有子树1,
: 返回结点个数1 .
|
|
