题解 | JAVA #二叉搜索树的最近公共祖先# [P2]

利用search tree的性质，在每个node上其实已经知道p和q分别在哪个child subtree。

对于一个node，以下三种情况可以直接确定该node就是LCA.

left里有一个target，root本身是一个target
right里有一个target, root本身是一个target
left, right里各有一个target

然后如果node不是LCA, 那么两个target要么都在left child, 要么都在right child.
所以只需要check其中的一边 (其实check的node都在一条确定的path上).
时间，空间复杂度都是O(h)
worst-case还是O(N), 如果tree是一条线。

import java.util.*;

public class Solution {
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
      return findLCA(root, Integer.MIN_VALUE, Integer.MAX_VALUE, p, q);
    }
  
    int findLCA(TreeNode root, int min, int max, int p, int q) {
      int numInLeft = root.left == null ? 0 : numInRange(min, root.val, p, q);
      int numInRight = root.right == null ? 0 : numInRange(root.val, max, p, q);
      
      // 三种情况下，root一定都是LCA 
      //   a. left里有一个，root有一个
      //   b. right里有一个, root有一个
      //   c. left, right里各有一个
      // 这个if其实涵盖了a,b,c三种情况
      if (numInLeft == 1 || numInRight == 1)
        return root.val;
      else if (numInLeft == 2)
        return findLCA(root.left, min, root.val, p, q);
      else // numInRight == 2
        return findLCA(root.right, root.val, max, p, q);
    }
    
    // Helper function that determines how many targets are in (min, max) - 左开右开
    int numInRange(int min, int max, int p, int q) {
      if ((p > min && p < max) && (q > min && q < max))
         return 2;
      if ((p > min && p < max) || (q > min && q < max))
        return 1;
      else 
        return 0;
    }
}