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

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

问题简述

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

思路1：树形DP（后序遍历）

• 考虑判断结点 x 是否为 o1 和 o2 的最近公共祖先需要从左右子节点获取哪些信息；

  • has_o1：是否存在 o1

  • has_o2：是否存在 o2

  • ret：是否已经找到最近公共祖先

• 然后根据子节点的以上信息，生成当前节点的这些信息，并返回；

• 详见代码；

Python

class Solution:
    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        
        from dataclasses import dataclass
        
        @dataclass
        class Info:
            has_o1: bool  # 以当前结点为根节点的树中是否存在 o1
            has_o2: bool  # 以当前结点为根节点的树中是否存在 o2
            ret: int  # o1 和 o2 的最近公共祖先

        def dfs(x):
            if not x: return Info(False, False, None)
            
            l, r = dfs(x.left), dfs(x.right)
            has_o1 = l.has_o1 or r.has_o1 or x.val == o1
            has_o2 = l.has_o2 or r.has_o2 or x.val == o2
            ret = l.ret or r.ret or x.val if has_o1 and has_o2 else None
            return Info(has_o1, has_o2, ret)
        
        return dfs(root).ret

思路2：路径对比（后序遍历）

• 记录从 o1 和 o2 到根节点的路径，找到两个路径上最后一个相同的节点；

• 因为是后序遍历，为了顺序比较所有祖先，可以考虑使用队列头插来保存节点；

Python

class Solution:
    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        
        def dfs(x, o, path):  # 获取 o 的祖先路径
            if not x: return False
            l, r = dfs(x.left, o, path), dfs(x.right, o, path)
            if l or r or x.val == o: 
                path.appendleft(x.val)
                return True
            return False
        
        from collections import deque
        p1 = deque(); dfs(root, o1, p1)
        p2 = deque(); dfs(root, o2, p2)
        
        pre = -1
        for v1, v2 in zip(p1, p2):
            if v1 == v2: pre = v1
            else: break
                
        return pre