LeetCode-235-NearestCommonAncestorofBinarySearchTree

NearestCommonAncestorofBinarySearchTree题目描述：给定一棵二叉搜索树，找到树中两个指定节点的最近公共祖先。百度百科对最近共同祖先的定义是：“对于有根树T的两个节点p和q，最近共同祖先表示为节点x，满足x是p和q的祖先，深度为x尽可能大（一个节点也可以是它自己的祖先）。”例子见LeetCode官网。来源：LeetCode链接：https://leetcode-cn.com/probl...版权归LeetCode所有。商业转载请联系官方授权，非商业转载请注明出处。方案一：递归法首先，如果p或q是根节点，则直接返回根节点。如果p和q都不是根节点，会在以下情况下处理：如果p和q的值都小于root的值，则递归调用lowerCommonAncestor方法，入参为root。左边。如果p和q的值都小于root的值，则递归调用方法lowestCommonAncestor，入参为root.right。如果p和q其中一个的值大于root，另一个小于root，那么p和q的最近共同祖先只能是root，所以直接返回root。publicclassLeetCode_235{/***递归方法**@paramroot*@paramp*@paramq*@return*/publicstaticTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){//如果p或q是根节点，直接返回根节点if(p==root){returnp;}if(q==root){返回q;}if(p.valroot.val&&q.val>root.val){//如果p和q的值都大于root的值，递归调用这个方法，入参是root.right返回lowestCommonAncestor(root.right,p,q);}else{//如果p和q有一个值大于root，另一个小于root，那么p和q的最近共同祖先只能是root，所以returnroot直接returnroot;}}publicstaticvoidmain(String[]args){//初始化二叉搜索树TreeNoderoot=newTreeNode(6);树节点node_2=新树节点（2）；TreeNodenode_8=newTreeNode(8);root.left=node_2;root.right=node_8;root.left.left=newTreeNode(0);root.left.right=newTreeNode(4);root.left.right.left=newTreeNode(3);root.left.right.right=newTreeNode(5);root.right.left=newTreeNode(7);root.right.right=newTreeNode(9);//调用方法并返回结果TreeNoderesult=lowestCommonAncestor(root,node_2,node_8);System.out.println(result.val);}}【每日留言】不是境遇造就人，而是人境