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

ゝ一纸荒年。 2023-02-18 09:48 35阅读 0赞

# 题目来源 #

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

# 题目描述 #

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

# 题目解析 #

## 层次遍历 ##

*  层次遍历一次：使用一个map将各节点的父节点存储下来：key = 当前节点，value = 当前节点的父节点 。 注意： 如果为根节点，那么它的父节点是null
 *  初始化一个栈s1：将p的路径存储下来，比如p=6时，栈为：6 5 3
 *  初始化第二个栈s2：将q的路径存储下来，比如q=1时，栈为：1 2
 *  初始化一个pre节点，指向null，初始化一个size = Math.min(s1.szie, s2.szie)
 *  循环(size)弹出栈，并更新pre，直到第一个不相同的节点，那么pre就是要找到节点

/**
     * 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){
        
                return root;
            }
    
            HashMap<TreeNode, TreeNode> map = new HashMap<>();
            map.put(root, null);
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()){
        
                int size = queue.size();
                for (int i = 0; i < size; i++){
        
                    TreeNode top = queue.pop();
                    if (top.left != null){
        
                        queue.offer(top.left);
                        map.put(top.left, top);
                    }
                    if (top.right != null){
        
                        queue.offer(top.right);
                        map.put(top.right, top);
                    }
                }
            }
    
            // p、q 为不同节点且均存在于给定的二叉树中
            Stack<TreeNode> stack1 = new Stack<>();
            TreeNode key = p;
            stack1.push(key);
            while (map.get(key) != null){
        
                stack1.push(map.get(key));
                key = map.get(key);
            }
    
            Stack<TreeNode> stack2 = new Stack<>();
            key = q;
            stack2.push(key);
            while (map.get(key) != null){
        
                stack2.push(map.get(key));
                key = map.get(key);
            }
            
            int size = Math.min(stack1.size(), stack2.size());
            TreeNode pre = null;
            for (int i = 0; i < size; i++){
        
                TreeNode treeNode1 = stack1.pop();
                TreeNode treeNode2 = stack2.pop();
                if (treeNode1 == treeNode2){
        
                    pre = treeNode1;
                }else{
        
                    break;
                }
            }
            
            return pre;
        }
    }

![在这里插入图片描述][20200617110955459.png]

优化：其他我们可以不用遍历全部的树，只需要得到p和q的路径就可以了

/**
     * 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){
        
                return root;
            }
    
            HashMap<TreeNode, TreeNode> parent = new HashMap<>();
            parent.put(root, null);
    
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!(parent.containsKey(p) && parent.containsKey(q))){
         // //直到两个节点都找到为止。
                int size = queue.size();
                for (int i = 0; i < size; i++){
        
                    TreeNode top = queue.pop();
                    if (top.left != null){
        
                        queue.offer(top.left);
                        parent.put(top.left, top);
                    }
                    if (top.right != null){
        
                        queue.offer(top.right);
                        parent.put(top.right, top);
                    }
                }
            }
    
            HashSet<TreeNode> ancestors = new HashSet<>();
            while (p != null){
        
                ancestors.add(p);
                p = parent.get(p);
            }
    
            while (!ancestors.contains(q)){
        
                q = parent.get(q);
            }
    
    
            return q;
        }
    }

![在这里插入图片描述][20200617112002957.png]

## 递归 ##

首先，要想通过递归来实现，就需要先确定临界条件，那么临界条件是什么呢？换句话说，临界条件就是递归中能够直接返回的特殊情况，第一点则是最常见的“判空”，判断根结点是否是空节点，如果是，那么肯定就可以马上返回了，这是一个临界条件；再来考虑题意，在以root为根结点的树中找到p结点和q结点的最近公共祖先，那么特殊情况是什么呢？很显然，特殊情况就是根结点就等于q结点或p结点的情况，想一下，如果根结点为二者之一，那么根结点就必定是最近公共祖先了，这时直接返回root即可。由此看来，这道题就一共有三种特殊情况，root == q 、root == p和root==null，这三种情况均直接返回root即可。  
根据临界条件，实际上可以发现这道题已经被简化为查找以root为根结点的树上是否有p结点或者q结点，如果有就返回p结点或q结点，否则返回null。  
这样一来其实就很简单了，从左右子树分别进行递归，即查找左右子树上是否有p结点或者q结点，就一共有4种情况：

*  左子树和右子树均找没有p结点或者q结点；（这里特别需要注意，虽然题目上说了p结点和q结点必定都存在，但是递归的时候必须把所有情况都考虑进去，因为题目给的条件是针对于整棵树，而递归会到局部，不一定都满足整体条件）
 *  左子树上能找到，但是右子树上找不到，此时就应当直接返回左子树的查找结果；
 *  右子树上能找到，但是左子树上找不到，此时就应当直接返回右子树的查找结果；
 *  左右子树上均能找到，说明此时的p结点和q结点分居root结点两侧，此时就应当直接返回root结点了。  
    综上也不难写出结果了：  
    [参考][Link 1]

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

优化：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)    {
        
            if (root == null || root == p || root == q){
        
                return root;
            }
    
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            if (left != null && left != q && left != p){
        
                return left;
            }
    
            
            TreeNode right = lowestCommonAncestor(root.right, p, q);
    
            if (left != null && right != null){
        
                return root;
            }
    
            if (left == null){
        
                return right;
            }
    
            if (right == null){
        
                return left;
            }
    
            return null;
        }

[68 - II.]: https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200617113243129.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200617110955459.png]: https://img-blog.csdnimg.cn/20200617110955459.png
[20200617112002957.png]: https://img-blog.csdnimg.cn/20200617112002957.png
[Link 1]: https://blog.csdn.net/qq_28114615/article/details/85715017
[20200617123917925.png]: https://img-blog.csdnimg.cn/20200617123917925.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200617113105943.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70