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

本题是一道非常典型的算法题，虽然本身难度不高，但是非常有助于理解递归程序的特点，值得牢固掌握。

题目描述

原题链接如下： LeetCode 236 二叉树的最近公共祖先

题目大意

公共祖先的含义就是以答案的节点为根的子树同时包含两个输入节点，而且特别注意答案可以包含任何一个节点自身。

输入与输出

LeetCode 的二叉树都使用统一的数组表示法：

• 类似中序遍历的输出结果，根节点在前，而后是左右子树的内容
• 为了使数组内容无歧义，只有空叶子节点或最后的节点无需显式填入 null

示例输入为：

1
2
3
4
5
6
7
8
9

Input 1:
root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]
p = 5
q = 1

Input 2:
root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]
p = 5
q = 4

示例输出为：

1
2
3
4
5

Output 1:
3

Output 2:
5

本题两组示例输入是同一棵树，仅仅是两个待查询的节点不同，树的官方示意图如下：

解题思路

本题当然可以采用直接遍历的方式找出所有节点对应的父节点，然后存入哈希表中，接着就能自底向上遍历父节点路径找出答案。但是，这样的算法并没有在空间复杂度上有领先，实际复杂度也不优秀，而且实际代码较长也不便于理解，所以直接省略。

实际上，一旦涉及树的操作应当自然地联想到递归，尤其涉及类似节点查询地操作时，递归代码简洁且易读，应当是首选答案。

在设计递归算法时必须记得：有返回值的递归算法必定假设子问题的递归调用已解决，即有合法返回值（本题中左右子树的查询操作）。关键点在于：

• 设计合理的递归目标，即良好的返回值
• 找到递归终止条件
• 利用子问题的递归调用返回值构建当前问题的正确解

在本题中，可以设即返回结果是：当前树中是否包含任意一个待查节点，有则返回节点指针，无则返回 null。而且，我们要对当前树的左右子树都进行查询操作，这样根据两个返回结果的是否为空可以得到如下关系：

• 都为 null：当前树不包含两个待查节点，返回 null
• 都不是 null：两个待查节点分列两个子树之中，返回 root
• 只有一个为 null：两个待查节点必定在结果不是 null 的子树中，返回它即可

而终止条件通常很泛用也很简单:

• 根节点为 null 时返回 null
• 根节点就是任意待查节点时返回根节点

这个解法要遍历所有节点以查询节点位置，时间复杂度为 O(n)，递归算法要对每次查询进行函数栈记录，空间复杂度为 O(n)。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
        if (root == null) return null
        if (root == p || root == q) return root
        val left = lowestCommonAncestor(root.left, p, q)
        val right = lowestCommonAncestor(root.right, p, q)
        if (left == null) return right
        if (right == null) return left
        return root
    }
}