https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
-
递归
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if((root.val>p.val&&root.val<q.val)||(root.val<p.val&&root.val>q.val)||root==p||root==q) return root; if(root.val>p.val&&root.val>q.val) return lowestCommonAncestor(root.left,p,q); return lowestCommonAncestor(root.right,p,q); } -
非递归
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { //如果根节点和p,q的差相乘是正数，说明这两个差值要么都是正数要么都是负数，也就是说 //他们肯定都位于根节点的同一侧，就继续往下找 while ((root.val - p.val) * (root.val - q.val) > 0) root = p.val < root.val ? root.left : root.right; //如果相乘的结果是负数，说明p和q位于根节点的两侧，如果等于0，说明至少有一个就是根节点 return root; }
