HHot 100C++ 图解

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

中等 二叉树 在力扣上做

一句话套路后序:两侧都有即答案,否则返回非空那侧

题目描述

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

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

 

示例 1:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出:5
解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3:

输入:root = [1,2], p = 1, q = 2
输出:1

 

提示:

  • 树中节点数目在范围 [2, 105] 内。
  • -109 <= Node.val <= 109
  • 所有 Node.val 互不相同 。
  • p != q
  • p 和 q 均存在于给定的二叉树中。

思路

时间O(n)
空间O(h)

思路

返回值语义(背下来,一类题全通):

  • · 本结点为 null 或等于 p/q -> 直接返回本结点
  • · 左右都返回非空 -> p、q 分居两侧,本结点就是 LCA
  • · 只有一侧非空 -> 把那一侧的结果原样上传

注意

这题不是 BST!不能靠大小比较剪枝(那是 Q235)。

图解

6 5 7 2 4 3 0 1 8
二叉树(来自本仓库测试数据,nullopt 表示空位)

C++17 题解

src/08_binary_tree.cpp12 行
namespace lc0236 {
class Solution {
 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;  // 分叉点
    return left ? left : right;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q236_lca8 行
lc0236::Solution s;
TreeNode* t = buildTree({3, 5, 1, 6, 2, 0, 8, nullopt, nullopt, 7, 4});
CHECK_EQ(s.lowestCommonAncestor(t, findNode(t, 5), findNode(t, 1)), findNode(t, 3));
// p 是 q 的祖先时,LCA 就是 p 本身(本题允许这种输入)
CHECK_EQ(s.lowestCommonAncestor(t, findNode(t, 5), findNode(t, 4)), findNode(t, 5));
CHECK_EQ(s.lowestCommonAncestor(t, findNode(t, 7), findNode(t, 6)), findNode(t, 5));
CHECK_EQ(s.lowestCommonAncestor(t, findNode(t, 0), findNode(t, 8)), findNode(t, 1));
freeTree(t);

↑↓ 选择↵ 打开/ 随时唤起