2025/8/15
题目（medium）：
我的思路：
经过观察我们可以发现以下规律（下面会用LCA来代替公共祖先节点作为描述）
- 如果p，q分别位于左右子树，则LCA是当前树的根节点
- 如果p，q分别位于同一子树（左或者右），则LCA是在该子树中能够让p，q分开处于两个子树的树的根节点
例如这个6，8，它们分别处于以3为根节点的树的左右子树中，因此它们的LCA是3
再例如这个6，4，它们显然是处于以3为根节点的树的左子树当中。但是又处于以5为根节点的左右子树当中，因此它们的LCA是5
好啦有了如上的规律之后，我们就知道需要判断p，q所在的左右子树关系，而在之前根据先序遍历和中序遍历构造原树的题目中我们是知道可以用头节点+中序遍历数组来划分左右子树的区域的。
因此，我们的完整思路步骤如下：
①先构建中序遍历数组
②再构建由节点快速查询其在中序遍历中的索引值的字典
③先让指针curRoot指向根节点开始，先获取根节点的索引值，p,q的索引值，然后根据索引值判断p,q的所在子树关系。
④若p,q在不同子树，则当前指针curRoot所指节点即为LCA
⑤若p,q在同一子树，则把curRoot移动到该子树的根节点位置，然后重复步骤二三四
具体代码如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
#判断两个节点是否在同一子树下
#若在一颗树的左右子树中，则公共父节点是该树的根节点
#因此需要找到能够让这两个节点处于不同子树的树
#首先判断p q是否相等
if p == q:
return p
#然后构建中序遍历列表
inorderList = list()
def inorder(root):
if root is None:
return
inorder(root.left)
inorderList.append(root)
inorder(root.right)
#首先获取中序遍历数组
inorder(root)
#构建中序遍历快速获取索引的哈希表
index = {element:i for i,element in enumerate(inorderList)}
curRoot = root
while curRoot:
curRootIndex = index[curRoot]
pIndex = index[p]
qIndex = index[q]
#如果两个索引一样的，说明是自己
if pIndex == qIndex:
return p
#如果两个节点在不同的子树，则答案是该树的根节点
elif((pIndex <= curRootIndex and qIndex >= curRootIndex)
or (qIndex <= curRootIndex and pIndex >= curRootIndex)):
return curRoot
#否则需再来一次以找到能把这两个节点分到不同子树下的树
elif pIndex < curRootIndex and qIndex < curRootIndex:
curRoot = curRoot.left
elif pIndex > curRootIndex and qIndex > curRootIndex:
curRoot = curRoot.right
return None时间复杂度：O（N)
空间复杂度：O（N）
优化思路：
上述的规律其实我们可以感觉到似乎有一点递归的气息，且因为使用了一个列表存中序遍历节点顺序，一个字典存储对应索引位置，因此空间开销稍大。而如果转化为递归则有可能可以优化到O（N）以下。
再深入思考可以发现，如果一个节点是LCA，则说明这个节点是p或者q 或者 p,q分别在该节点作为根节点的树的左右子树上。
因此我们可以：
- 把输入看成是【根节点，p，q】
- 把输出看成是【LCA结果值（没有结果则为None）】
大致的步骤如下：
①定义递归终止条件为：根节点为空，或者根节点等于p或者q（说明这颗子树中包含了p 或者 q）
②在左子树中递归查找目标值
③在右子树中递归查找目标值
④如果左右子树都得到了一个目标值，则它们得到的值就是LCA
⑤如果只有一个得到了目标值，则只有该目标值就是LCA（如果都没有目标值，则说明该节点作为根节点的树的左右子树中都不存在p或者q )
具体代码如下：
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
#递归终止条件：根节点为空或者根节点为 p 或者 q，说明已经找到了目标节点
if not root or root == p or root == q:
return root
#如果搜索到了p或者q，则会返回p或者q，否则返回None说明p,q不在这颗子树上
left = self.lowestCommonAncestor(root.left, p, q) #递归地在左子树中试图搜索到p,q
right = self.lowestCommonAncestor(root.right, p, q) #递归地在右子树中试图搜索到p,q
#如果左右子树都能够返回一个节点，则说明p,q一定分别在这颗树的左右子树上
if left and right: # p 和 q 分居两侧，当前根为 LCA
return root
#否则说明p,q在同一颗子树，此时有一侧得到的是最深的公共节点
return left or right # 返回非空的一侧结果时间复杂度：O（N）
空间复杂度：O（H）
其他思路：
还可以用一种很直接的方式，就是直接让p,q都“往上跳”，如果第一次跳到了同一个节点，则说明它是LCA
步骤是：
①用一个哈希表和深度优先搜索来把以【节点：该节点的父节点】这个键值对来构造字典（注意根节点的父节点是None）
②再创建一个集合用于记录已经访问到的父亲节点
③先记录p指针指向的节点到集合中，然后让p指针根据哈希表逐步往上跳到当前节点的父节点，然后重复步骤三直到p指向None
④再把q指针指向的节点去判断是否在集合中， 若在则返回q，否则然后让q指针指向当前节点的父节点，然后重复步骤四直到q指向None
具体代码如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
#上跳寻找父节点
#首先用一个字典去存储每个节点对应的父节点
fatherNode = {}
#深度优先搜索来构造父节点字典
def dfs(root):
if(root.left):
fatherNode[root.left] = root
dfs(root.left)
if(root.right):
fatherNode[root.right] = root
dfs(root.right)
fatherNode[root] = None #根节点没有父亲
dfs(root)
#再创建一个用于判断当前父节点是否被访问到过集合
hasVisited = set()
while p:
hasVisited.add(p) #注意这里是每次把p指针所在位置加入集合
p = fatherNode[p]
while q:
if q in hasVisited: #这里每次用q指针指向的节点来进行判断
return q
q = fatherNode[q]
return None
时间复杂度：O（N）
空间复杂度：O（N）
总结：
①运用定义去观察条件之间的规律就更有可能做的出来题目。
②p,q的LCA就是能够让p,q位于左右子树的树的根节点
③有时候最简单的想法可能也有用的，比如最后一种父节点上跳法