面试算法-二叉树中找到两个节点的最近公共祖先（JAVA实现）

题干

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

数据范围：1≤n≤1000，树上每个节点的val满足 0<val≤100
要求：空间复杂度 O(1)，时间复杂度 O(n)

注：本题保证二叉树中每个节点的val值均不相同。

解题思路

一般情况下，对于二叉树的算法题大多可以通过递归的方法来解决。那这道题目如何来递归呢？利用子问题的解来求得最终解。根节点判断最近公共祖先的三种情况：

1. 最近公共祖先的解在左子树上
2. 最近公共祖先的解在右子树上
3. 左右子树各找到一个值，那么根节点就是最近公共祖先

递归结束的条件，满足下列其一即可：

1. 节点为null
2. 节点的值为o1
3. 节点的值为o2

因为只要该节点的值是其中一个查询条件的值，那么公共祖先就不可能再是它的子节点了，也就没有继续递归的必要了，直接返回该节点即可。

示例代码

publicclassSolution{/**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */publicint lowestCommonAncestor(TreeNode root,int o1,int o2){// write code herereturncommonAncestor(root,o1,o2).val;}publicTreeNodecommonAncestor(TreeNode root,int o1,int o2){if(root==null|| root.val== o1|| root.val==o2){return root;}TreeNode left=commonAncestor(root.left, o1, o2);TreeNode right=commonAncestor(root.right, o1, o2);return left==null? right:(right==null? left:root);}}

复杂度分析：最坏情况下，每个节点遍历一次，时间复杂度为O(n)；没有用到额外的存储空间，空间复杂度为O(1）。