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) {
          //如果根節(jié)點和p,q的差相乘是正數(shù)，說明這兩個差值要么都是正數(shù)要么都是負數(shù)，也就是說
          //他們肯定都位于根節(jié)點的同一側(cè)，就繼續(xù)往下找
          while ((root.val - p.val) * (root.val - q.val) > 0)
              root = p.val < root.val ? root.left : root.right;
          //如果相乘的結(jié)果是負數(shù)，說明p和q位于根節(jié)點的兩側(cè)，如果等于0，說明至少有一個就是根節(jié)點
          return root;
  }