甘肃网站建设推广做cpa的电影网站模板

二叉搜索树的最近公共祖先-力扣 235 题

求二叉搜索树最近公共祖先（祖先也包括自己）

前提：

1.节点值唯一

2.p和q都存在

要点：若 p，q 在 ancestor 的两侧，则 ancestor 就是它们的最近公共祖先

解题思路：

/*
            __ 6 __
           /       \
          2         8
         / \       / \
        0   4     7   9
           / \
          3   5
          比如：2与8的祖先有：2、8、6  而6是公共祖先也是最近的
          4与5的祖先有：4、5、2、6  公共祖先有4 2 6   最近的祖先是4
          我们利用这个结论：待查找节点 p q 在某一节点的两侧，那么此节点就是最近的公共祖先
          举一个特殊案例：4与5的祖先有：4、5、2、6  公共祖先有4 2 6 
          先判断6的两侧是不是4与5 如果不是 就进行下一个祖先两侧是否是4与5
          当然在这里，到后面判断4两侧是否是4与5的时候，我们也可以看作是在两侧 
     */

/*__ 6 __/       \2         8/ \       / \0   4     7   9/ \3   5比如：2与8的祖先有：2、8、6  而6是公共祖先也是最近的4与5的祖先有：4、5、2、6  公共祖先有4 2 6   最近的祖先是4我们利用这个结论：待查找节点 p q 在某一节点的两侧，那么此节点就是最近的公共祖先举一个特殊案例：4与5的祖先有：4、5、2、6  公共祖先有4 2 6 先判断6的两侧是不是4与5 如果不是 就进行下一个祖先两侧是否是4与5当然在这里，到后面判断4两侧是否是4与5的时候，我们也可以看作是在两侧 */
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {TreeNode ancestor = root;//ancestor.val > p.val && ancestor.val > q.val：p和q在当前节点的左边//ancestor.val < p.val && ancestor.val < q.val：p和q在当前节点的右边while (ancestor.val > p.val && ancestor.val > q.val || ancestor.val < p.val && ancestor.val < q.val) {if (ancestor.val > p.val) {//这个时候祖先值要开始靠近p或者qancestor = ancestor.left;} else {ancestor = ancestor.right;}}return ancestor;
}