长大后想做什么？做回小孩！

0%

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

发表于 分类于 Valine：
本文字数： 341

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

Y1WYHH.png

Y1WJDe.png

思路一：深搜 去根节点的左右子树中寻找 p 和 q 两个节点：

返回条件：如果左子树或右子树为空，则返回 null；如果左子树或右子树中找到了 p 或者 q ，这棵子树一定返回 p 或 q 。

递归分别去左右子树中深搜寻找 p 或 q，左右子树深搜的结果记为 left 、right ，深搜全部完成后，如果 left 为空，则结果只需要看 right 标记的节点(p 或 q)；如果 right 为空，只需要看 left ；如果 right 和 left 都不为空，这说明左右子树的根节点 root 是 p 和 q 的公共祖先，此时 p 和 q 分别在 root 的左右子树中，一边一个。

1
2
3
4
5
6
7
8
9
10
11
12
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    //base 子树中不存在 p 和 q ,或者子树中找到了 p 或 q
    if (root == null||root == p||root==q)return root;
    //到左右子树中寻找 p 或 q
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    //一边为空不存在 p 或 q,公共祖先一定是另一边标记的节点
    if (left==null)return right;
    if (right ==null)return left;
    //p 和 q 分别在子树根 root 的两侧各一个
    return root;
}

时间复杂度：O(n) 深度遍历

空间复杂度：O(n) 递归栈大小取决于树的深度，最坏情况树呈链表状

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github