Lihang Liu's Homepage > Archive > LeetCode 笔记 2：Binary Tree Lowest Common Ancestor

LeetCode 笔记 2：Binary Tree Lowest Common Ancestor

February 19, 2023

Loweset Common Ancestor

From wikipedia Lowest common ancestor - Wikipedia:

In graph theory and computer science, the lowest common ancestor (LCA) (also called least common ancestor) of two nodes v and w in a [tree]( https://en.wikipedia.org/wiki/Tree_ (graph_theory) “Tree (graph theory)") or directed acyclic graph (DAG) T is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).

概念很简单，举几个例子：

A 和 B 的 LCA 是 A；
B 和 C 的 LCA 是 A;
D 和 E 的 LCA 是 A;
E 和 I 的 LCA 是 C;
D 和 F 的 LCA 是 A;
G 和 H 的 LCA 是 D;
C 和 F 的 LCA 是 C;

思路

大部分的二叉树题目，首先想到的是递归的解法，这是因为二叉树的数据结构特点所致：我们只知道当前节点和当前节点的相连节点的信息，而不知道全局信息。

那么，如何求解给定的任意另个 Node X 和 Y 的 LCA 呢？思路是这样的：

我们从下往上，遇到 X 或者 Y 的时候，将它们返回给上层；遇到非 X 或者 Y 的节点则返回 null
当上层 Node 拿到两个非空节点是，当前节点即为 LCA ，将当前节点返回
当上层 Node 拿到一个空节点一个非空节点时，那个非空节点要么是 LCA , 要么是 X 或者 Y , 我们继续将非空节点返回给上层处理即可

因为对于任意给定的两个节点 X 或者 Y 来说，它们的 LCA ：

要么是 X 或者 Y 其中的一个，这表示其中一个节点位于另一个节点的子树之中；
要么是 X 或者 Y 的上层节点，这表示 X 和 Y 都位于它们的 LCA 子树之中。

而我们的算法在递归的过程中，至多只会遇到一次，左子树返回和右子树返回均不为空的情况；否则，我们将非空节点返回即可，该非空节点即为题目所求的 LCA ：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        
        if (root == p || root == q) {
            return root;
        }
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }
}

例题

Example 1

1123. Lowest Common Ancestor of Deepest Leaves

这道题是找出深度最深的所有叶子结点的 LCA ，只需分解成两个步骤：

找到最大深度（ DFS ）
找到最大深度叶子结点的 LCA

最大深度的叶子结点可能有多个，但这不妨碍我们算法的步骤和正确性：

对于最大深度的叶子结点，返回自身；
对非最大深度的节点，如果左子树返回和右子树返回均不为空，说明该节点为 LCA ，返回自身；否则返回左子树和右子树的非空返回；

解法：

class Solution {
    private int deepestDepth = 0;

    public TreeNode lcaDeepestLeaves(TreeNode root) {
        if (root.left == null && root.right == null) {
            return root;
        }
        findDeepestDepth(root, 0);
        return lca(root, 0);
    }

    private TreeNode lca(TreeNode root, int depth) {
        if (root == null) {
            return null;
        }

        TreeNode leftRet = lca(root.left, depth + 1);
        TreeNode rightRet = lca(root.right, depth + 1);

        if (depth == deepestDepth) {
            return root;
        }

        if (leftRet != null && rightRet != null) {
            return root;
        } else if (leftRet != null) {
            return leftRet;
        } else {
            return rightRet;
        }
    }

    private void findDeepestDepth(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        deepestDepth = Math.max(deepestDepth, depth);
        findDeepestDepth(root.left, depth + 1);
        findDeepestDepth(root.right, depth + 1);
    }
}

Example 2

235. Lowest Common Ancestor of a Binary Search Tree

这道题目的区别是，数据结构换成了 BST，根据 BST 的性质我们可以，对于任意节点 X 和 Y 来说，它们的 LCA 一定满足： X.val <= LCA.val && LCA.val <= Y.val 。

我们只要从上到下，递归地寻到满足这一布尔条件式的节点即可：

如果 LCA.val < X.val && LCA.val < Y.val ，那么当前节点的值太小，我们去右子树中递归寻找；
如果 LCA.val > X.val && LCA.val > Y.val ，那么当前节点值太大，我们去左子树中递归寻找；
否则，当前节点值落在了 X.val 和 Y.val 之间，说明当前节点即为我们要找的 LCA

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

LeetCode 笔记 2：Binary Tree Lowest Common Ancestor

Loweset Common Ancestor

思路

例题

LCA 题目