本文介绍: java
Problem: 236. 二叉树的最近公共祖先
💖 图解
时间复杂度, 示例：
O
(
n
)
O(n)
O(n)
空间复杂度, 示例：O
(
n
)
O(n)
O(n)
💖 AC code
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
// 公共祖先 本先：公共祖先 lca 必然是 p 的祖先 ，也是 q 的祖先
/**
* @param root 当前树的根
* @param p 查找的节点1
* @param q 查找的节点2
* @return 返回root树中离root节点最近的 p 或 q，返回null则表示无
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
{
// 找到 p 或 q 了，直接返回 p 或 q
if (root == null || root == p || root == q)// 空值，找到头了直接返回
return root;
// 左右递归
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null)// 说明当前树root 的左子树无 p或q
return right;// 则p，q同在右子树，取离root最近的
if (right == null)
return left;
// p，q分布在 root的左右子树上，当前 root 即为最近公共祖先（即左子树只有 p或q 一个，那它只能返回p 或 q，右子树同理）
return root;
}
}
原文地址:https://blog.csdn.net/lt6666678/article/details/135541584
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_55242.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
