微软近期高频面试题分享 + 分析（十）

二叉搜索树的最近公共祖先  解析

要利用二叉搜索树的性质
如果p和q都大于node值，则说明p和q在node的右子树中
如果p和q都小于node值，则说明p和q在node的左子树中
如果p小于node，q大于node值，则说明node即为p和q在二叉搜索树上的分叉口
也即最近公共祖先

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. 
    
11. class Solution {
    
12.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
13.         while(true){
    
14.             if(root.val <= Math.max(p.val, q.val) && root.val >= Math.min(p.val, q.val)){
    
15.                 break;
    
16.             }else if(root.val > Math.max(p.val, q.val)){
    
17.                 root = root.left;
    
18.             }else{
    
19.                 root = root.right;
    
20.             }
    
21.         }
    
22.         return root;
    
23.     }
    
24. }

复制代码

复杂度分析

• 时间复杂度：O(n)，其中 n*n* 是给定的二叉搜索树中的节点个数。分析思路与方法一相同。
• 空间复杂度：O(1)。
  

都是经典题！
最后一道还可以延伸为n-arry tree中两个节点的最近公共祖先