＃yyds干货盘点＃ 解决剑指offer：在二叉树中找到两个节点的最近公共祖先

1.简述：

描述

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。数据范围：树上节点数满足  , 节点值val满足区间 [0,n)要求：时间复杂度 注：本题保证二叉树中每个节点的val值均不相同。如当输入{3,5,1,6,2,0,8,#,#,7,4},5,1时，二叉树{3,5,1,6,2,0,8,#,#,7,4}如下图所示：所以节点值为5和节点值为1的节点的最近公共祖先节点的节点值为3，所以对应的输出为3。节点本身可以视为自己的祖先

示例1

输入：

登录后复制

      
      

       
       {3,5,1,6,2,0,8,#,#,7,4},5,1
      
      
      
      

       
       
1.
      
      

返回值：

登录后复制

      
      

       
       3
      
      
      
      

       
       
1.
      
      

示例2

输入：

登录后复制

      
      

       
       {3,5,1,6,2,0,8,#,#,7,4},2,7
      
      
      
      

       
       
1.
      
      

返回值：

登录后复制

      
      

       
       2
      
      
      
      

       
       
1.
      
      

2.代码实现：

登录后复制

      
      

       
       import java.util.*;
       
       

       
       
/*
       
       
 * public 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 helper(root, o1, o2).val;
       
       
    }
       
       

       
       
    public TreeNode helper(TreeNode root, int o1, int o2) {
       
       
        if (root == null || root.val == o1 || root.val == o2)
       
       
            return root;
       
       
        TreeNode left = helper(root.left, o1, o2);
       
       
        TreeNode right = helper(root.right, o1, o2);
       
       
        //如果left为空，说明这两个节点在root结点的右子树上，我们只需要返回右子树查找的结果即可
       
       
        if (left == null)
       
       
            return right;
       
       
        //同上
       
       
        if (right == null)
       
       
            return left;
       
       
        //如果left和right都不为空，说明这两个节点一个在root的左子树上一个在root的右子树上，
       
       
        //我们只需要返回cur结点即可。
       
       
        return root;
       
       
    }
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
       
       
23.
       
       
24.
       
       
25.
       
       
26.
       
       
27.
       
       
28.
       
       
29.
       
       
30.
       
       
31.
       
       
32.
       
       
33.
       
       
34.
       
       
35.
       
       
36.
       
       
37.
       
       
38.