面试题68 - I. 二叉搜索树的最近公共祖先

今天药忘吃喽~ 2023-02-18 10:58 13阅读 0赞

# 题目来源 #

[面试题68 - I. 二叉搜索树的最近公共祖先][68 - I.]

[235. 二叉搜索树的最近公共祖先][235.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

## 递归 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]

*  如果p，q都小于当前节点，那么最小公共祖先一定是在当前节点的左子树
 *  如果p，q都大于当前节点，那么最小公共祖先一定是在当前节点的右子树
 *  如果p，q的值刚好在当前节点的中间（值不等于当前节点），也就是说q，p一定是当前节点的左右两边，那么当前节点一定是最小公共祖先

## 深度优先搜索 ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            if (root == null || root == p || root == q){
        
                return root;
            }
    
            // 找到p的路径：
            TreeNode treeNode = root;
            List<TreeNode> list = new ArrayList<>();
            while (treeNode != null){
        
                list.add(treeNode);
                if (treeNode.val < p.val){
        
                    treeNode = treeNode.right;
                }else if (treeNode.val > p.val){
        
                    treeNode = treeNode.left;
                }else {
        
                    break;
                }
            }
    
            // p、q 为不同节点且均存在于给定的二叉搜索树中。
            treeNode = root;
            List<TreeNode> list1 = new ArrayList<>();
            while (treeNode != null){
        
                list1.add(treeNode);
                if (treeNode.val < q.val){
        
                    treeNode = treeNode.right;
                }else if (treeNode.val > q.val){
        
                    treeNode = treeNode.left;
                }else {
        
                    break;
                }
            }
    
            TreeNode pre = null;
            int size = Math.min(list.size(), list1.size());
            for (int i = 0; i < size; i++){
        
                if (list.get(i).val == list1.get(i).val){
        
                    pre = list.get(i);
                }else{
        
                    return pre;
                }
            }
    
    
    
            return pre;
        }
    
    }

[68 - I.]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[235.]: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200617154724170.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200617154544749.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70