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

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;




    }
}