using System; using System.Collections.Generic; /* public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode (int x) { val = x; } } */ 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 if(root==null) return -1; if(root.val==o1 ||root.val==o2){ return root.val; } int left=lowestCommonAncestor(root.left, o1, o2); int right=lowestCommonAncestor(root.right, o1, o2); if(left==-1) return right; if(right==-1) return left; return root.val; } }
代码没啥好说的,参考别人的思路写的;关键在于分析一个节点如何满足条件。
1.如果一个节点就是o1或者o2 ,那么直接返回,
2.否则o1,o2 分散再该节点的子节点,可能分居左右两侧,可能分居一侧,也可能不存在
抓住上面两点,递归就好。