2024.2.9力扣每日一题——二叉树的最近公共祖先

题目来源

力扣每日一题；题序：236

我的题解

方法一 后序遍历

后序遍历可以携带一些子节点信息，通过后序遍历可以知道节点p和节点q在根节点的哪个子节点出现。

时间复杂度：O(n)。
空间复杂度：O(n)。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 n，因此空间复杂度为 O(n)

TreeNode res=null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    find(root,p,q);
    return res;
}
public boolean find(TreeNode root,TreeNode p,TreeNode q){
    if(root==null){
        return false;
    }
    //看p或者q是否在左子树出现
    boolean lson=find(root.left,p,q);
    //看p或者q是否在右子树出现
    boolean rson=find(root.right,p,q);
    //lson&&rson表示p和q分别出现在root的左右子树上
    //(root==p||root==q)&&(lson||rson) 表示root就是p或者q，并且q或p在root的某一个子树上
    if((lson&&rson)||((root==p||root==q)&&(lson||rson))){
        res=root;
    }
    return lson||rson||(root==p||root==q);
}

方法二 存储父节点（哈希表+List）

类似并查集的操作。这里使用哈希表存储每个节点的父节点，然后利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是要找的最近公共祖先。
具体做法：

• 从根节点开始遍历整棵二叉树，用哈希表记录每个节点的父节点指针。
• 从 p 节点开始不断往它的祖先移动，并用数据结构记录已经访问过的祖先节点。
• 同样，再从 q 节点开始不断往它的祖先移动，如果有祖先已经被访问过，即意味着这是 p 和 q 的深度最深的公共祖先，即 LCA 节点。

时间复杂度：O(n)
空间复杂度：O(n)

Map<TreeNode,TreeNode> map=new HashMap<>();
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
   dfs(root,null);
   List<TreeNode> hasVisited=new ArrayList<>();
   //找寻p节点的所有祖先节点
   TreeNode pParent=map.get(p);
   //注意p本身是最近公共祖先节点
   hasVisited.add(p);
   while(pParent!=null){
       hasVisited.add(pParent);
       pParent=map.get(pParent);
   }
   //注意q本身就是最近公共祖先节点
   if(hasVisited.contains(q))
       return q;
   //遍历q的祖先节点
   TreeNode qParent=map.get(q);
   while(qParent!=null){
       if(hasVisited.contains(qParent))
           return qParent;
       qParent=map.get(qParent);
   }
   return root;
}
//存储父节点
public void dfs(TreeNode root,TreeNode parent){
   if(root==null)
       return ;
   map.put(root,parent);
   dfs(root.left,root);
   dfs(root.right,root);
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~