面试：二叉树中找到两个节点的最近公共节点

题干：

给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

示例：

输入：

[3,5,1,6,2,0,8,#,#,7,4],5,1

输出：3

分析

如果两个节点都分布在根节点的一颗子树上，那么公共祖先一定是更高节点的父节点。如果两个节点分别在根节点的左右子树上，那么公共祖先一定是该树的根节点。

代码实现

class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; } public class Solution { /** * * @param root TreeNode类 * @param o1 int整型 * @param o2 int整型 * @return int整型 */ public int lowestCommonAncestor (TreeNode root, int o1, int o2) { return lowestCommonAncestorAssis(root, o1, o2).val; } private TreeNode lowestCommonAncestorAssis(TreeNode root, int o1, int o2){ if (root == null || root.val == o1 || root.val == o2){ return root; } TreeNode left = lowestCommonAncestorAssis(root.left, o1, o2); TreeNode right = lowestCommonAncestorAssis(root.right, o1, o2); //都在右子树 if(left == null){ return right; } //都在左子树 if(right == null){ return left; } //左右两边都有 return root; } }