algorithm - 具有任意大小的递归调用的算法的运行时间

我已经写了下面的算法，给定一个节点x在一个二叉搜索树t中，将设置字段s为所有节点在子树的根在x，这样对于每个节点，s将是所有奇数键在子树的根在该节点。

OddNodeSetter(T, x):
    if (T.x == NIL):
        return 0;
    if (T.x.key mod 2 == 1):
        T.x.s = T.x.key + OddNodeSetter(T, x.left) + OddNodeSetter(T, x.right)
    else:
        T.x.s = OddNodeSetter(T, x.left) + OddNodeSetter(T, x.right)

我想用主定理来解决这个问题

T(n) = T(k) + T(n-k-1) + 1 for 1 <= k < n

但是，由于这两个递归调用的大小可能因k和n-k-1（即x的左、右子树中的节点数）的不同而不同，因此我无法很好地解决这个递归问题。例如，如果x的左子树和右子树中的节点数相等，我们可以用

T(n) = 2T(n/2) + 1

这很容易解决，但这并不能证明所有情况下的运行时间。
有没有可能用主定理证明这个算法在o（n）中运行，如果没有，还有什么其他方法可以做到这一点？

最佳答案

该算法只访问树中的每个节点一次，因此为o（n）。
更新：
显然，访问需要固定的时间（不包括递归调用）。