六曲阑干偎碧树，杨柳风轻，展尽黄金缕。

68. 树中两个节点的最低公共祖先

68.1 二叉查找树

题目链接

Leetcode : 235. Lowest Common Ancestor of a Binary Search Tree

解题思路

在二叉查找树中，两个节点 p, q 的公共祖先 root 满足 root.val >= p.val && root.val <= q.val。


public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null)
        return root;
    if (root.val > p.val && root.val > q.val)
        return lowestCommonAncestor(root.left, p, q);
    if (root.val < p.val && root.val < q.val)
        return lowestCommonAncestor(root.right, p, q);
    return root;
}

68.2 普通二叉树

题目链接

Leetcode : 236. Lowest Common Ancestor of a Binary Tree

解题思路

在左右子树中查找是否存在 p 或者 q，如果 p 和 q 分别在两个子树中，那么就说明根节点就是最低公共祖先。


public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q)
        return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    return left == null ? right : right == null ? left : root;
}

版权声明：如无特别声明，本站收集的文章归  cs-notes  所有。 如有侵权，请联系删除。

联系邮箱： GenshinTimeStamp@outlook.com

本文标题：《 68. 树中两个节点的最低公共祖先 》

本文链接：/%E9%9D%A2%E8%AF%95%E5%88%B7%E9%A2%98/%E5%89%91%E6%8C%87offer%E9%A2%98%E8%A7%A3/%E9%A2%98%E8%A7%A3/68.-%E6%A0%91%E4%B8%AD%E4%B8%A4%E4%B8%AA%E8%8A%82%E7%82%B9%E7%9A%84%E6%9C%80%E4%BD%8E%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html

Contents