Lowest Common Ancestor of a BST
你得到了一棵以堆顺序存储在数组 tree 中的二叉搜索树：根节点位于索引 0，索引 i 的子节点位于 2*i+1（左侧）和 2*i+2（右侧），-1 表示空位置。节点左子树中的所有值都小于该节点的值，右子树中的所有值都大于该节点的值。
编写 lowestCommonAncestor，返回树中值 p 和 q 的最近公共祖先的值：也就是同时包含这两个值的子树中最深的节点。节点属于自己的子树，因此如果 p 位于 q 的上方，答案就是 p。
函数
- treeinteger-array
- 按层序遍历二叉搜索树，空位置用 -1 表示
- pinteger
- 要查找的第一个值
- qinteger
- 要查找的第二个值
- 返回值integer
- 其子树中同时包含 p 和 q 的最深节点的值
约束条件
1 ≤ tree.length ≤ 32767- 每个
tree[i]都是-1，或是满足0 ≤ tree[i] ≤ 105的值。 tree[0]永远不会是-1，因此树至少有一个节点。- 数组可能在最后一个节点之后，以额外的
-1项结束。 - 空位置的两个子节点也都是空的，深度最多为
14。 - 这棵树是有效的二叉搜索树，因此其中所有值都不相同。
p和q是树中节点的值。它们的顺序任意，也可能相等。
示例
- 输入
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
- 输出
- 8
- 解释
- 从
3和15向上遍历，它们首先到达的共同节点是8：3是它的左子节点，而15位于右侧的12下方。根节点20也是共同祖先，但位置更高。
- 输入
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
- 输出
- 12
- 解释
10是12的左子节点，而且一个节点也算作自己的祖先，所以12包含这两个值，而它下面的节点都不包含。这里p是较大的值。
- 输入
- tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
- 输出
- 70
- 解释
- 这两个值都大于根节点
50，所以它们都在根节点的右侧。到了70，它们分开了：55较小，位于左侧，在60的下方，而80较大。
进阶
如果 p 或 q 可能不在树中，并且函数在这种情况下必须返回 -1，你会做哪些修改？
提示
逐个打开提示，每个都会多透露一点。
站在根节点。如果
p和q都小于它的值，那么这两个节点都在哪个子树中？只要这两个值都在当前节点的同一侧，下面每个更深层的公共祖先也都在那一侧。第一个不在同一侧，或节点本身包含其中一个值的节点，就是你要找的节点。
从索引
0开始。当两个值都小于tree[i]时，移动到2*i+1；当两个值都大于tree[i]时，移动到2*i+2。否则，返回tree[i]。
题解
搜索树会告诉你每个节点中值的位置：较小的在左边，较大的在右边。从根节点出发，沿着同时包含这两个值的一侧前进。它们不再位于同一侧的第一个节点就是答案，你可以沿着一条路径到达它。
搜索整棵树，不考虑顺序
思路
这个方法适用于任何二叉树。递归函数 find(i) 会报告节点 i 的子树中包含什么。包含 p 或 q 的节点会报告自身：如果另一个值在它的下方，它就是答案；否则，更高处的某个节点会同时看到这两个值。其他节点会询问两个子节点。如果两个子节点都有返回结果，说明 p 和 q 位于不同的分支，这个节点就是它们相遇的位置；如果只有一个子节点有返回结果，就把结果向上传递。
对于 3 和 15，节点 8 从左边得到索引 3，从右边得到索引 10，然后报告自身。它可能会访问每个节点：时间复杂度为 O(n)，递归的空间复杂度为 O(h)。
算法
- 编写
find(i)。如果i处为空（超出末尾或为-1），则返回-1。 - 如果
tree[i]是p或q，则返回i。 - 对
2*i+1和2*i+2调用find。如果两边都找到了内容，则返回i。 - 否则，返回找到内容的一侧，或者返回
-1。 - 返回
tree[find(0)]。
def lowestCommonAncestor(tree, p, q):
n = len(tree)
def find(i):
# In the subtree at index i: the index of the answer if both values are
# inside, the index of the one that is, or -1 when neither is.
if i >= n or tree[i] == -1:
return -1
if tree[i] == p or tree[i] == q:
return i
left = find(2 * i + 1)
right = find(2 * i + 2)
if left != -1 and right != -1:
return i # one value on each side: this node is the answer
return left if left != -1 else right
return tree[find(0)]比较两条搜索路径
思路
按常规方式查找一个值：从根节点开始，如果它小于当前节点，就向左走；如果它大于当前节点，就向右走。从根节点到某个节点的路径是唯一的，因此遍历会经过该值的所有祖先节点，不会经过其他节点。
记录两条遍历路径。它们会经过相同的节点，直到对应的值走向不同的方向，因此共同的起始部分列出了公共祖先节点，其中最后一个值就是最低公共祖先。对于 3 和 15，路径分别是 20, 8, 3 和 20, 8, 12, 15：它们共有 20, 8，所以答案是 8。每条遍历路径每层走一步：时间复杂度为 O(h)，列表需要 O(h) 的空间。
算法
- 编写
path(target)：从索引0开始，记录tree[i]；如果它等于target，就停止，否则当target较小时移动到2*i+1，较大时移动到2*i+2。 - 分别构建到
p和q的路径。 - 从头开始遍历两个列表，并返回它们共有的最后一个值。
def lowestCommonAncestor(tree, p, q):
def path(target):
# The values met on the way from the root down to target.
values = []
i = 0
while True:
values.append(tree[i])
if tree[i] == target:
return values
i = 2 * i + 1 if target < tree[i] else 2 * i + 2
to_p, to_q = path(p), path(q)
# Both paths start at the root; the answer is the last value they share.
answer = to_p[0]
for a, b in zip(to_p, to_q):
if a != b:
break
answer = a
return answer向下遍历，直到值分开
思路
当 p 和 q 朝同一方向移动时，两条路径会重合，所以同时沿着两条路径前进。在值为 v 的节点处，如果两个值都更小，它们都在左子树中，v 下方的每个公共祖先也都在左子树中：向左走。如果两个值都更大，就向右走。
否则，一个值更小，另一个更大，因此 v 的任何一个子节点都不会同时包含它们，或者其中一个值等于 v，而 v 是它自身的祖先。无论哪种情况，v 都是位于两者上方的最深节点。在第三个例子中，50 小于两个值，所以向右走到 70，此时 55 更小，80 更大。每一层进行一组比较，时间复杂度为 O(h)，空间复杂度为 O(1)。
算法
- 从索引
i = 0开始。 - 读取
v = tree[i]。 - 如果
p < v且q < v，移动到2*i+1并重复。 - 如果
p > v且q > v，移动到2*i+2并重复。 - 否则返回
v。
def lowestCommonAncestor(tree, p, q):
i = 0 # start at the root
while True:
value = tree[i]
if p < value and q < value:
i = 2 * i + 1 # both are smaller: the answer is on the left
elif p > value and q > value:
i = 2 * i + 2 # both are larger: the answer is on the right
else:
return value # they split here, or one of them is this node
易错点和边界情况
- 在移动测试中使用
≤和≥。当p = 12且q = 10时，遍历会越过12到达10，然后返回10或者走出树的范围。 - 假设
p < q。在第二个示例中，p的值更大。将它们分别与节点比较，或者先交换它们。 - 返回索引而不是值。答案是
tree[i]，不是i。 - 在 Lua 和 R 中，数组从 1 开始。节点索引仍使用从 0 开始的计数方式，以便进行
2*i+1运算，并读取tree[i + 1]。
常见问题3
BST 中最近公共祖先的时间复杂度是多少？
从根节点开始沿着一条路径遍历，因此对于深度为 h 的树，时间复杂度为 O(h)，额外空间复杂度为 O(1)。对于平衡树，时间复杂度为 O(log n)；对于形状像一条单独路径的树，时间复杂度为 O(n)。
二叉搜索树中的 LCA 与二叉树中的 LCA 有什么不同？
在普通二叉树中，值可能位于任意位置，因此你可能需要搜索每个节点，工作量为 O(n)。在搜索树中，将两个值与节点进行比较，就能判断它们分别位于哪一侧，因此你只需从根节点沿着一条路径查找。
一个节点可以是它自己的最近公共祖先吗？
是的。一个节点也算作自己的祖先，所以当 p 位于 q 上方时，答案是 p；当两个值相等时，答案就是该值。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def lowestCommonAncestor(tree, p, q):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15] p = 3 q = 15
预期输出
8