236_二叉树的最近公共祖先

类型：树

二叉树的最近公共祖先 💛 ⭐

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

❓ 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。（一个节点也可以是它自己的祖先。）

💡 递归

一般情况下，两个结点 p 和 q 的最近公共祖先 r 满足如下情况：p 和 q 分别位于 r 的左子树和右子树中。

特殊情况下，p 是 q 的子树，则二者的最近公共祖先就是 q；q 是 p 的子树，则二者的最近公共祖先就是 p。

我们用 f(x) 表示 x 为根的子树中是否包含 p 或 q 结点。则综合以上两种情况的表达式可以表示为：

(f(lson) and f(rson)) or ((x == p or x == q) and (f(lson) or f(rson)))

其中 f(lson) and f(rson) 代表一般情况，(x == p or x == q) and (f(lson) or f(rson)) 代表特殊情况。

class Solution:
    def __init__(self):
        self.ans = None

    def dfs(self, root, p, q):
        if not root:
            return False
        lson = self.dfs(root.left, p, q)
        rson = self.dfs(root.right, p, q)
        if (lson and rson) or ((root.val == p.val or root.val == q.val) and (lson or rson)):
            self.ans = root
        return (lson or rson or root.val == p.val or root.val == q.val)

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.dfs(root, p, q)
        return self.ans

时间复杂度：O(n)，空间复杂度：O(n)

💡 存储父结点

我们利用哈希表存储所有结点的父结点，利用此父结点信息从 p 不断往上跳，并记录期间访问过的结点，再从 q 结点往上跳，如果碰到已经访问过的结点，那么这个结点就是我们要找的最近公共祖先。

class Solution {
    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
    Set<Integer> visited = new HashSet<Integer>();

    public void dfs(TreeNode root) {
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while (p != null) {
            visited.add(p.val);
            p = parent.get(p.val);
        }
        while (q != null) {
            if (visited.contains(q.val)) {
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }
}

时间复杂度：O(n)，空间复杂度：O(n)