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

本文主要是介绍2024.2.9力扣每日一题——二叉树的最近公共祖先，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2024.2.9

- - 题目来源
  - 我的题解
  - - 方法一后序遍历
    - 方法二存储父节点（哈希表+List）

题目来源

力扣每日一题；题序：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);
}