‍博客主页：@花无缺
欢迎 点赞 收藏⭐ 留言 加关注✅!
本文由 花无缺 原创

收录于专栏 【力扣题解】

文章目录

  • 【力扣题解】P236-二叉树的最近公共祖先-Java题解
    • 题目描述
    • 题解
    • 总结

【力扣题解】P236-二叉树的最近公共祖先-Java题解

P236-二叉树的最近公共祖先

题目描述

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

百度百科中最近公共祖先的定义为：“对于有根树 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 均存在于给定的二叉树中。

题解

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 空树, 返回 null// 当前节点是 p 节点, 那么直接返回 p, 说明 p 就是 p, q 的祖先节点// 当前节点是 q 节点, 那么直接返回 q, 说明 q 就是 p, q 的祖先节点if (root == null || root == p || root == q) {return root;}// 递归遍历左子树和右子树// 搜索左子树和右子树中是否有 p 或 qTreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);// 如果左右子树的搜索结果都不为空, 说明 p 和 q 都在左右子树中找到了// 当前节点肯定就是 p, q 的祖先节点, 直接返回 rootif (left != null && right != null) {return root;}// 如果 left 为空, right 不为空, 那么祖先节点就在右子树中// 结果就是 right, 直接返回if (left == null && right != null) {return right;// 如果 left 不为空, right 为空, 那么祖先节点就在左子树中// 直接返回 left} else if (left != null && right == null) {return left;// 否则 left 和 right 都为空// 说明没有找到公共祖先, 返回 null} else {return null;}}

时间复杂度：O(n)，要搜索整个二叉树，遍历所有节点，节点数为 n。

总结

这个题目要求我们查找两个节点的最近公共祖先节点，那么我们肯定需要自底向上的搜索节点，因为只有自底向上的搜索才会找到两个节点最近的公共祖先节点，那么我们就想到了回溯，先遍历最底层的节点，如果不满足条件，再回溯到上层的节点查找，那么我们就可以使用后序遍历（左右中），后序遍历就是很自然的回溯过程。

此处我们使用的是递归的写法，那么递归的终止条件如何确定呢？首先假设我们从根节点开始出发，如果当前节点是空节点，说明这是一棵空树，那么递归肯定要终止，并且返回 null。另外，如果根节点就是 p 节点或者 q 节点，那么 p 和 q 的公共祖先节点就是根节点，因为如果根节点就是 p（q），那么另外一个节点 q（p）肯定就是当前节点（根节点）的子节点，所以根节点就是公共祖先节点。

所以递归的终止条件为：

// 空树, 直接返回 nullif (root == null) {return null;}// 当前节点是 p 节点, 那么直接返回 p, 说明 p 就是 p, q 的祖先节点// 当前节点是 q 节点, 那么直接返回 q, 说明 q 就是 p, q 的祖先节点if (root == p || root == q) {return root;}

接下来我们就要进行后序遍历了，先遍历左子树，再遍历右子树：

而且我们要将左右子树递归的结果保存下来，因为在回溯到中间节点的时候，我们需要使用左右子树递归的结果。

TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);

然后遍历中间节点：

如果说左右子树返回的结果都不为空，那么说明左右子树都分别找到了 p 和 q 节点，那么说明当前节点就是他们的最近公共祖先节点。

如果有一个子树的结果为空，那么说明他们的祖先节点就在另一棵子树，那么直接返回另一棵子树的结果。

如果两棵树都为空，那么说明搜索完了整棵树都没有找到符合题意的公共祖先，直接返回 null；

// 如果 left 为空, right 不为空, 那么祖先节点就在右子树中// 结果就是 right, 直接返回if (left == null && right != null) {return right;// 如果 left 不为空, right 为空, 那么祖先节点就在左子树中// 直接返回 left} else if (left != null && right == null) {return left;// 否则 left 和 right 都为空// 说明没有找到公共祖先, 返回 null} else {return null;}

作者：花无缺(huawuque404.com)

欢迎关注我的博客：花无缺-每一个不曾起舞的日子都是对生命的辜负~
一起进步-刷题专栏：【力扣题解】
往期精彩好文：
【全网最全爱心代码仓库】
【CSS选择器全解指南】
【HTML万字详解】
你们的点赞 收藏⭐ 留言 关注✅
是我持续创作，输出优质内容的最大动力！
谢谢！