java版本剑指offer：在二叉树中找到两个节点的最近公共祖先
描述
给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
注：本题保证二叉树中每个节点的val值均不相同。
示例1
输入：
[3,5,1,6,2,0,8,#,#,7,4],5,1
返回值：
3
方法一：递归
- 这颗树的某个节点等于节点o1或o2，就向上返回这个节点给父节点
- 当前节点的左右子树返回值分别是o1、o2，当前这个节点就是最近公共祖先
- 当前节点只有一个子树的返回值为o1或o2节点，则返回该值
- 当前节点的两个子树返回值都为空，则返回空指针
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) {
// write code here
TreeNode node = find(root,o1,o2);
retur服务器托管网n node == null ? null:node.val;
}
public TreeNode find(TreeNode root,int o1,int o2){
//出口条件
if(root==null || root.val == o1 || root.val == o2)
return root;
//递归调用
TreeNode left = find(root.left,o1,o2);
TreeNode right = find(root.right,o1,o2);
//当某节点左右都看完，加入判断条件，返回上一层
if(left!=null&&right!=null) return root;
else if(left==null && right!=null) return right;
else if(left!=null && right==null) return left;
else return null;
}
}方法二：中序遍历
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整型
*/
//一个全局的list来存放中序遍历结果
ArrayList list = new ArrayList();
public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
// w服务器托管网rite code here
midOrders(root);
//用一个hashmap来记录每一个结点值对应的下标
HashMap map = new HashMap();
for(int i=0;ik&&map.get(o2)>k){
root=root.right;
}else{
return root.val;
}
}
return -1;
}
public void midOrders(TreeNode root){
if(root==null){
return;
}
midOrders(root.left);
list.add(root.val);
midOrders(root.right);
}
}服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net 机房租用，北京机房租用服务器托管网，IDC机房托管， http://www.fwqtg服务器托管网.net相关推荐: 使用 StarCoder 创建一个编程助手如果你是一个软件开…
