有返回值的树遍历函数

Question

我有这个函数来检查从节点到叶子的路径的键的总和是否总是低于某个值 k，如果不是这种情况，则将标志设置为 1 以跟踪那。

是否可以创建此 int 或 bool 类型的函数并使其 return 0 如果 sum 总是 < than k 并且如果存在 sum >= k 的情况而不使用像这样的标志则为 1我在做什么？

int flag=0;
void checkSum(Node node,int sum,int k){
    if(node==nullptr){
        return;
    } 
    sum=sum+node->key;
    if(node->left==nullptr && node->right==nullptr){
        if(sum>=k){
            flag=1;
        }
        return;
    }
    checkSum(node->left,sum,k);
    checkSum(node->right,sum,k);
    
}

Answer 1

怎么样：

bool checkSum(Node *node, int sum, int k){
    if (node == nullptr) return true;
    sum += node->key;
    if (sum >= k) return false;
    return checkSum(node->left, sum, k) && checkSum(node->right, sum, k);
}

如果您在没有 returning false 的情况下到达 nullptr，因此在路径上没有超过 k，您可以 return true 返回给调用者。如果在任何时候 sum 超过 k 你可以 return false，这将短路进一步的递归调用并由于 && 运算符一直传播回根。因此，树以 dfs 方式进行探索，并且只要路径和超过 k，returns false 返回到根，否则它 returns true。

但是，此实现假定非负节点键。如果这不能假设，以至于你真的只想检查叶节点的总和，你可以将其修改为：

bool checkSum(Node *node, int sum, int k) {
    if (!node->left && !node->right)
        return sum < k;
    sum += node->key;
    return checkSum(node->left, sum, k) && checkSum(node->right, sum, k);
}

有返回值的树遍历函数

Tree traversal function with returning value

algorithm

binary-tree

tree-traversal