题解 | #在二叉树中找到两个节点的最近公共祖先#

在二叉树中找到两个节点的最近公共祖先

http://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116

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 ancestor = dfs(root, o1, o2);
        return ancestor.val;
    }
    public TreeNode dfs(TreeNode root, int o1, int o2){
        if(root == null) return null;
        if(root.val == o1 || root.val == o2) return root;


        TreeNode l = dfs(root.left, o1, o2);
        TreeNode r = dfs(root.right, o1, o2);
        // 要么在一个节点的左右子树中,要么某一个节点是另一个节点的祖先节点。        

        if(l != null && r !=null) return root;
        return l == null ? r:l;




    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 18:06
点赞 评论 收藏
分享
一表renzha:手写数字识别就是一个作业而已
点赞 评论 收藏
分享
06-10 21:15
门头沟学院 Java
宁阿:好多这种没🧠的公司,他们估计都不知道毕业的人不能给安排实习岗
实习吐槽大会
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务