二叉树最近公共祖先问题

喜欢ヅ旅行 2022-10-05 04:41 177阅读 0赞

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。  
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”  
![在这里插入图片描述][2021060612434076.png]

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
    输出：3
    解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

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

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
    输出：5
    解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

/**
     * 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) {
        
       //注意 p,q 必然存在树内 ，且所有的节点的值唯一
       //递归思想 以root为根的子树进行查找p和q, 如果root==null ||p|| q 直接返回root
       //表示对于当前树的查找已经完毕，否则对左右子树进行查找，根据左右子树返回值判断
       //1.左右子树的返回值都不为null 此时 root为LCA
       //2.如果左右子树只有一个不为null，说明只有p和q存在于最先找到的哪个节点为LCA
       //3.左右子树的返回值均为null p,q均不在树中返回null
       if(root==null ||root==p|| root==q ) return root;
       TreeNode left=lowestCommonAncestor(root.left,p,q);
       TreeNode right=lowestCommonAncestor(root.right,p,q);
       if(left==null &&right==null) return null;
       else if(left!=null &&right!=null) return root;
       else return  left ==null ? right :left;
            
        }
    }

思路2：

思路：用哈希表存储所有节点的父节点，然后我们就可以用节点的父节点信息从 p节点
         不断的往上跳，并记录已经访问过的节点，再从q节点开始不断的往上跳，如果碰到已经访问过的节点 就是我们要找的最近公共祖先
       算法： 1、从根节点开始遍历整颗二叉树，用哈希表记录每个节点的父节点指针
             2、从p节点开始不断往他的祖先移动 ，并用数据结构记录已经访问过的祖先节点
             3、我们再从q节点开始不断往他的祖先移动，如果有祖先已经被访问过，即意味着这是 p 和 q 的深度最深的公共祖先，即 LCA 节点。
    class Solution {
        
        Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
        Set<Integer> visited = new HashSet<Integer>();
    
        public void dfs(TreeNode root) {
        
            if (root.left != null) {
        
                parent.put(root.left.val, root);
                dfs(root.left);
            }
            if (root.right != null) {
        
                parent.put(root.right.val, root);
                dfs(root.right);
            }
        }
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            dfs(root);
            while (p != null) {
        
                visited.add(p.val);
                p = parent.get(p.val);//得到父节点
            }
            while (q != null) {
        
                if (visited.contains(q.val)) {
        
                    return q;
                }
                q = parent.get(q.val);//得到父节点
            }
            return null;
        }
    }

[2021060612434076.png]: /images/20221005/7a6862f6668c47d785c47345b777df0b.png
[20210606124421710.png]: /images/20221005/9e836a858da6486e9d3c88b9af3c7302.png