在二叉树中找到两个节点的最近公共祖先-牛客

思路

1、递归

1. 若结点为空，直接返回-1
   2）若结点值等于o1或o2，返回当前结点值
   3）1、2皆不是，分别在左子树、右子树中递归找公共祖先
   4）若左子树中没有，则在右子树中；若右子树中没有，则在左子树中；若左右子树都没有，则当前结点值就是公共祖先

class Solution:
    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        # 递归:深度优先搜索
        if root==None:
            return -1
        #当前结点值等于某个目标值
        if o1==root.val or o2==root.val:
            return root.val
        #左子树找公共祖先
        left=self.lowestCommonAncestor(root.left, o1, o2)
        #右子树找公共祖先
        right=self.lowestCommonAncestor(root.right, o1, o2)
        #左子树没找到，则在右子树中
        if left==-1:
            return right
        #右子树没找到，则在左子树中
        if right==-1:
            return left
        #否则，是当前结点
        return root.val
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2、路径比较法
1）利用DFS分别求根节点到o1的路径、根节点到o2的路径
2）比较两个路径，最后一个相同点，就是最近的公共祖先

• 深度优先搜索DFS
  涉及递归
  1）递归终止条件：root为空或flag为真(找到了路径)，
  2）入参和返回值：入参：root，path，o（目标结点的值）；返回值：从根节点到目标结点的路径
  3）本层任务：path中加入当前结点值，当前结点值==目标值，直接返回；
  否则，遍历左子树、右子树查找路径，找到后将flag变为true;若该子树没有目标结点，回溯，path.pop

# class Solution:
#     # 法2：路径比较法：深度优先搜索
#     # 记录是否找到到o的路径
#     flag = False 
#     # 求得根节点到目标节点的路径
#     def dfs(self, root: TreeNode, path: List[int], o: int): 
#         if self.flag or not root:
#             return
#         path.append(root.val)
#         # 节点值都不同，可以直接用值比较
#         if root.val == o: 
#             self.flag = True
#             return
#         # dfs遍历查找
#         self.dfs(root.left, path, o) 
#         self.dfs(root.right, path, o)
#         #找到
#         if self.flag:
#             return
#         # 该子树没有，回溯
#         path.pop() 
        
#     def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
#         path1, path2 = [], []
#         # 求根节点到两个节点的路径
#         self.dfs(root, path1, o1) 
#         # 重置flag，查找下一个
#         self.flag = False 
#         self.dfs(root, path2, o2)
#         i = 0
#         res = None
#         # 比较两个路径，找到第一个不同的点
#         while i < len(path1) and i < len(path2): 
#             if path1[i] == path2[i]: 
#                 # 最后一个相同的节点就是最近公共祖先
#                 res = path1[i] 
#                 i += 1
#             else:
#                 break
#         return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40