2023年6月22日发(作者：)

⼆叉树最近公共祖先问题给定⼀个⼆叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表⽰为⼀个节点 x，满⾜ x 是 p、q 的祖先且 x 的深度尽可能⼤（⼀个节点也可以是它⾃⼰的祖先）。”输⼊：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出：3解释：节点 5 和节点 1 的最近公共祖先是节点 3 。输⼊：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(,p,q); TreeNode right=lowestCommonAncestor(,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 parent = new HashMap(); Set visited = new HashSet(); public void dfs(TreeNode root) { if ( != null) { (, root); dfs(); } if ( != null) { (, root); dfs(); } } public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { dfs(root); while (p != null) { (); p = ();//得到⽗节点 } while (q != null) { if (ns()) { return q; } q = ();//得到⽗节点 } return null; }}