leetcode 235. Lowest Common Ancestor of a Binary Search Tree | 235. 二叉搜索树的最近公共祖先（哈希表）

落日映苍穹つ 2022-08-30 11:26 98阅读 0赞

## 题目 ##

[https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/][https_leetcode.com_problems_lowest-common-ancestor-of-a-binary-search-tree]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

> 哈希表解法思路来自左程云《程序员代码面试指南》

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][20210720002125533.png]

/** * 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) { 
            HashMap<TreeNode, TreeNode> map = new HashMap<>();
            preOrder(root, map);
    
            HashSet<TreeNode> set = new HashSet<>();
            TreeNode pNode = p;
            set.add(root);
            while (pNode != root) { 
                set.add(pNode);
                pNode = map.get(pNode);
            }
    
    
            TreeNode qNode = q;
            while (true) { 
                if (set.contains(qNode)) return qNode;
                qNode = map.get(qNode);
            }
        }
    
        public void preOrder(TreeNode node, Map<TreeNode, TreeNode> map) { 
            if (node.left != null) { 
                map.put(node.left, node);
                preOrder(node.left, map);
            }
            if (node.right != null) { 
                map.put(node.right, node);
                preOrder(node.right, map);
            }
        }
    }

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

[https_leetcode.com_problems_lowest-common-ancestor-of-a-binary-search-tree]: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/8aef72727627413db4c56038762076af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/c870518fa07c46a793b915a7ebcd5156.png
[20210720002125533.png]: /images/20220829/1cb85ffebca741b4868e55c6e6675999.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/b848986783ea49ada039f204ceff6a65.png