给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。
解法 1
对二叉树进行中序遍历，如果 p 在当前节点的左子树且 q 在当前节点的右子树；或者当前节点为 p 或 q 的其中一个，且另一个在当前节点的左子树或右子树中，那么当前节点即为 p 和 q 的最近公共祖先。
class Solution:
def __init__(self):
# Variable to store LCA node.
self.ans = None
def lowest_common_ancestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def recurse_tree(root):
# If reached the end of a branch, return False.
if not root:
return False
# Left Recursion
left = recurse_tree(root.left)
# Right Recursion
right = recurse_tree(root.right)
# If the current node is one of p or q
mid = root == p or root == q
# If any two of the three flags left, right or mid become True.
if mid + left + right >= 2:
self.ans = root
# Return True if either of the three bool values is True.
return mid or left or right
# Traverse the tree
recurse_tree(root)
return self.ans
执行用时 :84 ms
内存消耗 :28.8 MB
时间复杂度：O(n)，最坏的情况遍历二叉树所有 n 个节点。
空间复杂度：O(n)，递归堆栈使用的最大空间位，斜二叉树的高度可以是 n。
解法 2
通过广度优先遍历所有节点，将由当前节点值和当前父节点值组成的键值对放入父指针字典中，可以利用该字典获取父节点，将 p 到 root 路径上的节点放入祖先集合，再遍历 q 到 root 路径上的节点，出现在祖先集合中的第一个相同节点即为 p 和 q 的最近公共祖先。
def lowest_common_ancestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# Stack for tree traversal
stack = [root]
# Dictionary for parent pointers
parent = {root.val: None}
# Iterate until we find both the nodes p and q
while p not in parent or q not in parent:
node = stack.pop()
# While traversing the tree, keep saving the parent pointers.
if node.left:
parent[node.left.val] = node.val
stack.append(node.left)
if node.right:
parent[node.right.val] = node.val
stack.append(node.right)
# Ancestors set() for node p.
ancestors = set()
# Process all ancestors for node p using parent pointers.
while p:
ancestors.add(p)
p = parent[p]
# The first ancestor of q which appears in
# p's ancestor set() is their lowest common ancestor.
while q not in ancestors:
q = parent[q]
return q
执行用时 :88 ms
内存消耗 :18 MB
时间复杂度：O(n)，在最坏的情况下，我们可能会访问二叉树的所有节点
空间复杂度：O(n)，在堆栈使用的最坏情况下，每个节点的父指针字典和祖先集合的空间为 n，斜二叉树的高度可能为 n
如果将题目中的二叉树限定为二叉搜索树呢？
二叉搜索树（BST）的性质如下：
- 节点 NN 左子树上的所有节点的值都小于等于节点 NN 的值
- 节点 NN 右子树上的所有节点的值都大于等于节点 NN 的值
- 左子树和右子树也都是 BST
解法 1
递归法，根据二叉搜索树的性质，我们可以肯定，最近公共祖先的值一定在 p 和 q 之间或恰好等于 p 或 q，所以可以从 root 节点开始迭代，若当前节点大于 p 和 q 则通过递归在左子树中搜索，若当前节点小于 p 和 q 则通过递归在右子树中搜索，若上述两个条件都不符合，则当前节点是第一个值恰好在 p 和 q 之间的节点，或者就是 p 或 q 节点的其中一个，且另一个在当前节点的左子树或右子树中，那么当前节点即为 p 和 q 的最近公共祖先，如下图所示：
def lowest_common_ancestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p.val < root.val > q.val:
return lowest_common_ancestor(root.left, p, q)
if p.val > root.val < q.val:
return lowest_common_ancestor(root.right, p, q)
return root
执行用时 :88 ms
内存消耗 :17.9 MB
时间复杂度：O(n)，其中 n 为 BST 中节点的个数，在最坏的情况下我们可能需要访问 BST 中所有的节点。
空间复杂度：O(n)，所需开辟的额外空间主要是递归栈产生的，n 是 BST 的高度。
解法 2
和解法 1 原理一样，也可以用迭代实现。
def lowest_common_ancestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while True:
if p.val < root.val > q.val:
root = root.left
elif p.val > root.val < q.val:
root = root.right
else:
return root
执行用时 :84 ms
内存消耗 :17.9 MB
时间复杂度：O(n)，其中 n 为 BST 中节点的个数，在最坏的情况下我们可能需要遍历 BST 中所有的节点。
空间复杂度：O(1)
参考
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
