如何计算该二叉搜索树验证程序的时间复杂度？

• 首先给出结论：你认为复杂度为O(N)的结论是正确的，统计得到的11次调用和你推导的O(2N)和O(N)并不冲突，O(2N)会按照大O表示法的规则化简为O(N)。
• 调用次数为11的原因：
  你给出的测试用例中，二叉树一共有5个非空节点，根据二叉树的基础性质：N个节点的二叉树的空指针域数量固定为N+1。
  你的funcUtil函数会对所有传入的节点（包括空节点）执行一次调用，所以总调用次数=非空节点调用次数 + 空节点调用次数 = N + (N+1) = 2N+1。代入N=5的情况，总调用次数为2*5+1=11，和你统计的结果完全一致。
• 大O表示法的化简规则：
  大O时间复杂度描述的是算法运行开销随输入规模增长的渐近趋势，计算过程中会忽略所有常数系数、常数项和低阶项。因此2N的常数系数2会被直接忽略，最终的复杂度为O(N)，不存在O(2*N)这种标准写法。
• 扩展说明：
  这段代码是标准的递归版二叉搜索树合法性校验实现，不管二叉树是什么结构，算法都只会遍历每个节点和对应空指针各一次，时间复杂度稳定为O(N)；空间复杂度由递归栈深度决定，最坏情况（树退化为单链表）为O(N)，平衡二叉树场景下为O(logN)。

内容的提问来源于stack exchange，提问作者user15329767