描述
给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 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 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; } // 如果right为空,说明这两个节点在root节点左子树上,只需要返回左子树查询的结果即可 if(right == null){ return left; } // 如果右子树和左子树都不为空,说明这两个节点一个在root的左子树上,一个在root的右子树上 // 只需要返回当前节点即可 return root; } }