Lowest Common Ancestor of a Binary Tree
你会得到一个以数组 root 表示的二叉树，节点按堆顺序排列：根节点位于索引 0，索引 i 的左、右子节点分别位于 2*i+1 和 2*i+2，空位置用 -1 表示。节点值互不相同，且没有特定顺序。
返回 p 和 q（两个不同节点的值）的最低公共祖先的值，也就是子树同时包含这两个节点的最深节点。子树包含其顶部节点，因此如果 q 位于 p 的下方，答案就是 p。
函数
- rootinteger-array
- 按层序排列的二叉树，其中 -1 表示空位置
- pinteger
- 一个节点的值
- qinteger
- 另一个节点的值
- 返回值integer
- 其子树同时包含 p 和 q 的最低节点的值
约束条件
2 ≤ root.length ≤ 32767- 每个
root[i]都是-1，或满足0 ≤ root[i] ≤ 104的值。 root[0]永远不会是-1，而且树至少有两个节点。- 数组的末尾可能会在最后一个节点之后多出一些
-1项。 - 空位置的两个子节点也都是空的，且深度最多为
14。 - 树中的所有值都各不相同，并且没有遵循任何顺序。
p和q是树中两个不同节点的值，顺序任意。
示例
- 输入
- root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 6q = 9
- 输出
- 3
- 解释
6是3的左子节点，9位于4的下方，在3的右侧，所以它们在3处相遇。比较值会指向根节点8：6更小，9更大。
- 输入
- root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 4q = 7
- 输出
- 4
- 解释
7是4的左子节点，而4的子树包括4本身，所以答案是4。
- 输入
- root = [1, -1, 6, -1, -1, 3, 0, -1, -1, -1, -1, -1, -1, -1, -1]p = 3q = 0
- 输出
- 6
- 解释
- 根节点
1没有左子节点。它的右子节点6的左边是3，右边是0，因此这些值在6处汇合。
进阶
如果 p 或 q 可能不存在，并且用 -1 作为答案，那么单次遍历中的哪种快捷方法会失效？你又如何仍然只遍历一次就完成？
提示
逐个打开提示，每个都会多透露一点。
在第一个示例中试试搜索树规则：
6小于根节点8，而9更大。它们实际位于哪里？这说明在这棵树中比较值时要注意什么？让每棵子树告诉它的父节点自己找到了什么：什么都没有、两个值之一，或者答案。如果一个节点从两个子节点那里都听到了一个值，那么
p和q就在这里相遇。编写一个递归的
find(i)，如果位置为空则返回-1，如果root[i]是p或q，则返回i；如果两个子节点都返回索引，则返回i；否则返回不为-1的子节点结果。答案是root[find(0)]。
题解
没有固定顺序告诉你值在哪一侧，所以你得自己查看。后序遍历一次，就能让每棵子树报告它发现的内容，这些值会在第一个同时收到两侧信息的节点处相遇。
沿路向下走，逐一搜索两侧
思路
从根节点向下遍历，在每个节点检查左子树中是否有 p 和 q。两者都在左边：向左走。两者都不在：向右走。各有一个：两个值分开了，这个节点就是答案。存有 p 或 q 的节点也可以作为答案，因为另一个值一定在它的下方。对于 6 和 9，根节点发现两者都在左边，而在 3 处，唯一的 6 只存有 p。
每向下一步都要搜索整棵子树，因此 h 层的代价是 O(n·h)；对于没有深度限制的高而窄的树，代价是 O(n²)。在 8 处搜索时，已经访问了 3 下方的所有节点，而在 3 处又会重复访问其中一些节点。
算法
- 编写
contains(i, value)：如果位置为空（超出末尾或为-1），返回false；如果root[i]等于value，返回true；否则检查两个子节点。 - 从
i = 0开始。如果root[i]是p或q，就返回它。 - 如果
2*i+1处的左子树中包含这两个值，就移到那里。如果其中一个值也不包含，就移到2*i+2处。 - 否则返回
root[i]。
def lowestCommonAncestor(root, p, q):
n = len(root)
def contains(i, value):
# Is value somewhere in the subtree at index i?
if i >= n or root[i] == -1:
return False
if root[i] == value:
return True
return contains(2 * i + 1, value) or contains(2 * i + 2, value)
i = 0 # p and q are always inside the subtree at i
while True:
if root[i] == p or root[i] == q:
return root[i] # one value is here, the other is below it
left = 2 * i + 1
p_left = contains(left, p)
q_left = contains(left, q)
if p_left and q_left:
i = left # both on the left
elif not p_left and not q_left:
i = 2 * i + 2 # both on the right
else:
return root[i] # one on each side一次后序遍历
思路
让每个子树从底向上只回答一次。find(i)：如果索引为 i 的子树同时包含两个值，就返回答案的索引；如果只包含 p 或 q，就返回它的索引；如果两个都不包含，就返回 -1。
包含 p 或 q 的节点无需查看下方，就返回自己的索引。如果另一个值在它的子树中，这个节点就是答案；如果不在，上层节点就会从两侧都收到结果。其他节点会同时询问两个子节点。两个结果表示这两个值分别来自不同侧，并在此相遇。单个结果则原样向上传递，无论它代表其中一个值还是最终答案。
在第一个示例中，3 从左侧收到索引 3，从右侧收到 10，然后返回自己的索引 1，根节点再将它向上传递。每个节点只访问一次：时间复杂度为 O(n)，递归深度为 O(h)。
算法
- 如果索引超出末尾，或者索引对应的值是
-1，find(i)会返回-1。 - 值为
p或q的节点会返回i，不再向下查找。 - 其他节点会计算
left = find(2*i+1)和right = find(2*i+2)。如果两者都不是-1，就返回i；否则返回那个不是-1的值，或者返回-1。 - 返回
root[find(0)]。
def lowestCommonAncestor(root, p, q):
n = len(root)
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 root[i] == -1:
return -1
if root[i] == p or root[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 root[find(0)]
易错点和边界情况
- 将值与节点进行比较。树没有顺序：在第一个示例中，遍历会在根节点
8处停止，而不是3。 - 向上传递
true或false，而不是索引。父节点无法判断最终答案是否已经在它的下方。 - 读取子节点前不检查长度。索引
10处的9有子节点索引21和22，超出了最后一个条目。 - 返回
find(0)（一个索引），而不是root[find(0)]。 - 在 Lua 和 R 中，数组从 1 开始：节点索引保持从 0 开始，并读取
root[i + 1]。
常见问题3
二叉树的最近公共祖先的时间复杂度是多少？
后序遍历最多访问每个节点一次：时间复杂度为 O(n)。递归栈每层保存一个栈帧，因此在平衡树中空间复杂度为 O(log n)，在形状像路径的树中为 O(n)。
这与二叉搜索树中的最近公共祖先有什么不同？
在搜索树中，将 p 和 q 与某个节点比较，就能知道它们分别在哪一侧，因此从根节点沿一条路径查找，就能在 O(h) 时间内找到答案。这里的比较无法提供任何信息，所以你需要搜索子树。
你能利用父指针找到最近公共祖先吗？
是的。在这个数组中，索引 i 的父节点是向下取整后的 (i-1)/2。将两个索引中较大的那个移到它的父节点，直到它们相等；较大的索引永远不会是较小索引的祖先。对于链式节点，将 p 的祖先放入一个集合中，然后从 q 开始向上查找，直到找到其中第一个祖先。
def lowestCommonAncestor(root, p, q):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9] p = 6 q = 9
预期输出
3