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

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

递归实现

解题思路

当我们从根节点往下遍历时，对于遍历到的节点来说祖先节点只有两种情况：

1. 一种是两个节点在同一边，此时祖先节点必然在它们都在的一边，如上图遍历在根节点时的B和H
2. 第二种是两个节点分别在两边，此时该节点就是它们的祖先节点，直接返回，如上图遍历在根节点时的D和I

实现的思路

1. 找节点p和q，如果找到了就返回，当某个节点左边找到了p和q之一，右边也找到了p和q之一，说明此时为第二种情况，该节点作为祖先节点直接返回即可。
2. 如果发现某个节点左边找到了p或q，右边没找到，说明上传上来的这个节点就是祖先节点

代码

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        if(root == null)return null;
        if(root == p)return p;
        if(root == q)return q;
        TreeNode l = lowestCommonAncestor(root.left,p,q);
        TreeNode r = lowestCommonAncestor(root.right,p,q);
        if(l != null && r != null)return root;
        if(l != null)return l;
        else return r;
    }
}

• 时间复杂度 O(n)
• 空间复杂度 O(n)