LeetCode 235/236 LCA最近公共祖先问题 递归题解，再次深入理解DFS、左右子树同时查找。

题目

235. 二叉搜索树的最近公共祖先

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

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

利用BST的性质遍历

思路

BST的一个关键性质是：

1

root.left.val < root.val < root.right.val

借由这个性质，查找LCA，可以分为如下情况：

  1. root在p、q中间：root为lca
  2. root在p、q左侧：root转移到root.left
  3. root在p、q右侧：root转移到root.right

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

复杂度分析

时间

整个过程最多遍历完整个树：复杂度O(n)。

空间

使用while(true)替换了递归，无额外空间占用，空间复杂度O(1)。

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

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

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

DFS同时向左右子树查找

思路

同时去左右子树上匹配p、q：

  1. root已经是某个节点，说明root就是两个节点的LCA；
  2. 左右子树均有匹配节点，说明公共祖先在root上；
  3. 只有左子树匹配到了p、q之一，说明右子树上没有p、q祖先；
  4. 只有右子树匹配到了p、q之一，说明左子树上没有p、q祖先；

当然，如果题干给定可能无LCA的入参，那么左右子树的dfs戳到底，返回的就是null。

此类题目，我觉得理解到同时DFS左右子树为精髓。

代码

 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
41
42
43
44

    static class DFS {

        /**
         * 同时去左右子树上匹配p、q
         * 1. root已经是某个节点，说明root就是两个节点的LCA；
         * 2. 左右子树均有匹配节点，说明公共祖先在root上；
         * 3. 只有左子树匹配到了p、q之一，说明右子树上没有p、q祖先；
         * 4. 只有右子树匹配到了p、q之一，说明左子树上没有p、q祖先；
         * <p>
         * 当然，如果题干给定可能无LCA的入参，那么左右子树的dfs戳到底，返回的就是null。
         */
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            return dfs(root, p, q);
        }

        /**
         * 从root树上找p或者q，找到则返回对应节点
         * root树包含了：左右子树
         */
        private TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) {
                // 已经戳到底了
                return null;
            }
            // 当前遍历节点已经找到了
            if (root.val == p.val || root.val == q.val) {
                return root;
            }
            // 左子树是否有对应节点？
            TreeNode leftFound = dfs(root.left, p, q);
            // 右子树是否有对应节点？
            TreeNode rightFound = dfs(root.right, p, q);
            if (leftFound != null && rightFound != null) {
                // 左右子树均有匹配节点，说明公共祖先在root上
                return root;
            }
            if (leftFound != null) {
                // 只有左子树匹配到了p、q之一，说明右子树上没有p、q祖先
                return leftFound;
            }
            // 只有右子树匹配到了p、q之一，说明左子树上没有p、q祖先
            return rightFound;
        }
    }

复杂度分析

时间

整个过程最多遍历完整个树：复杂度O(n)。

空间

递归主要为栈的开销，最差情况下树退化为链表，空间复杂度O(n)。