关于leetcode235题中复杂度的疑问
来源：7-7 二分搜索树中的问题 Lowest Common Ancestor of a Binary Search Tree
v不离不弃v
2020-03-19
波波老师，关于leetcode235中递归解法，您给的复杂度是O（logn）和O(1)，这里的时间复杂度和空间复杂度是不是一样的都是树的高度呢，为啥这里空间复杂度是O（1）我有一些不理解。。时间复杂度和遍历的树的节点有关但是这题由于只需要判断每个根节点所以是，递归需要利用系统栈相当于递归了几次空间复杂度就是几次，感觉复杂度也是树的高度就是logn。
然后我觉得复杂度不是应该是最坏的条件呢？如果这棵树如果变成一个链表的话，那么时间复杂度和空间复杂度不应该最坏的条件都是O(n)?
写回答
1回答
-
liuyubobobo
2020-03-19
你是对的。我写的不准确。
时间复杂度说最坏是 O(n) 没问题，因为树可能退化。
非递归算法的空间复杂度是 O(1)。因为这个问题的非递归算法不需要额外的栈存储搜索路径上的所有节点。但是递归算法的空间复杂度也可以看做是 O(n)。
继续加油！：）
00
相似问题