给定BST三个节点验证祖孙关系，时间复杂度为何是O(h)而非O(logn)？

• O(logn)是平衡BST的特殊场景复杂度，不是所有BST的通用属性。普通BST没有强制平衡约束，树的结构完全由节点插入顺序决定，最坏情况下会退化成单链表，此时树高h等于总节点数n，O(logn)的复杂度完全不成立。用O(h)表述可以覆盖所有BST结构的场景，不管是平衡的最优情况还是退化成链表的最坏情况，都适用。只有红黑树、AVL树这类带平衡机制的BST，才能保证h始终在logn级别，这种场景下O(h)和O(logn)是等价的。
• 你的算法核心是多次BST路径查找：不管是判断祖先还是后代，每次查找都只会沿着一条从起始节点到目标节点的路径向下走，每一步只会往下移动一层，最多走的步数就是树的高度h。整套逻辑最多执行3次查找操作，总操作数最多为3h，按照复杂度计算省略常数的规则，最终复杂度就是O(h)。
• 算法复杂度标注会优先选择最通用严谨的表述：如果题目没有明确说明输入为平衡BST，就不能默认h等于logn，标注O(h)比O(logn)更严谨，不会对不同场景下的算法效率产生误导。

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