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

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

1.简述：

描述

示例1

输入：

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

返回值：

3

示例2

输入：

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

返回值：

2

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; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。