f*******r
发帖数: 1086 | 1 有一个面试题目就是对于一个bst，
check是否存在 Root to leaf path sum equal to a given number:
以下是geeksforgeeks上的样例代码:
int hasPathSum(struct node* node, int sum)
{
// return true if we run out of tree and sum==0
if (node == NULL) {
return(sum == 0);
}
else {
// otherwise check both subtrees
int subSum = sum - node->data;
return(hasPathSum(node->left, subSum) ||
hasPathSum(node->right, subSum));
}
}
我自己也写了类似的code，但是测试发现貌似不对，比如如果我有一个
bst如 |
r****o
发帖数: 1950 | 2 是不是在倒数第2个1的时候，它的右节点是NULL，hasPathSum()就会返回true。
【在 f*******r 的大作中提到】
: 有一个面试题目就是对于一个bst，
: check是否存在 Root to leaf path sum equal to a given number:
: 以下是geeksforgeeks上的样例代码:
: int hasPathSum(struct node* node, int sum)
: {
: // return true if we run out of tree and sum==0
: if (node == NULL) {
: return(sum == 0);
: }
: else {
|
f*******r
发帖数: 1086 | 3 对
就是这个case
！
【在 r****o 的大作中提到】
: 是不是在倒数第2个1的时候，它的右节点是NULL，hasPathSum()就会返回true。
|
r****o
发帖数: 1950 | 4 能不能看看我写的对不对?
bool hasPathSum(struct node* node, int sum)
{
// return true if we run out of tree and sum==0
if (node == NULL) {
return(sum == 0);
}
else {
// otherwise check both subtrees
int subSum = sum - node->data;
if ((node->left&&node->right)||(!node->left && !node->right))
return(hasPathSum(node->left, subSum) || hasPathSum(node->right,
subSum));
else if (node->left)
return hasPathSum(node->left, s
【在 f*******r 的大作中提到】
: 有一个面试题目就是对于一个bst，
: check是否存在 Root to leaf path sum equal to a given number:
: 以下是geeksforgeeks上的样例代码:
: int hasPathSum(struct node* node, int sum)
: {
: // return true if we run out of tree and sum==0
: if (node == NULL) {
: return(sum == 0);
: }
: else {
|
f*******r
发帖数: 1086 | 5 我刚刚check过应该没问题了：）
和我想的改进差不多，把所有的条件都check一下
只是看到网上到处流传一个错误的code，想确认一下
自己的想法是否有问题，非常感谢的！
【在 r****o 的大作中提到】
: 能不能看看我写的对不对?
: bool hasPathSum(struct node* node, int sum)
: {
: // return true if we run out of tree and sum==0
: if (node == NULL) {
: return(sum == 0);
: }
: else {
: // otherwise check both subtrees
: int subSum = sum - node->data;
|
r****o
发帖数: 1950 | 6 多谢，呵呵。
【在 f*******r 的大作中提到】
: 我刚刚check过应该没问题了：）
: 和我想的改进差不多，把所有的条件都check一下
: 只是看到网上到处流传一个错误的code，想确认一下
: 自己的想法是否有问题，非常感谢的！
|
