DeepSeek LeetCode 236. 二叉树的最近公共祖先 Java实现

LeetCode 236. 二叉树的最近公共祖先 Java 实现

思路：递归后序遍历

从根节点开始递归：

· 如果当前节点为空，或当前节点就是 p 或 q，直接返回当前节点。
· 分别递归左右子树，得到 left 和 right。
· 如果 left 和 right 都非空，说明 p 和 q 分别在左右两侧，当前节点就是最近公共祖先。
· 否则，返回非空的那一个（说明两个目标节点都在同一侧，或只找到了其中一个）。

Java 代码

classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){// 递归终止条件if(root==null||root==p||root==q){returnroot;}// 后序遍历：先处理左右子树TreeNodeleft=lowestCommonAncestor(root.left,p,q);TreeNoderight=lowestCommonAncestor(root.right,p,q);// 左右都找到了，说明 p、q 分布在两侧，当前节点就是 LCAif(left!=null&&right!=null){returnroot;}// 否则返回非空的那一侧returnleft!=null?left:right;}}

复杂度分析

· 时间复杂度：O(n)，每个节点最多访问一次。
· 空间复杂度：O(h)，递归栈深度为树高。最坏情况下（链状树）为 O(n)。

示例

// 树结构：// 3// / \// 5 1// / \ / \// 6 2 0 8// / \// 7 4p=5,q=1→3p=5,q=4→5p=6,q=4→5

关键点

· 递归函数含义：在以 root 为根的子树中，寻找 p 和 q 的最近公共祖先。
· 如果当前节点就是 p 或 q，直接返回它，因为不可能再往下找到更近的祖先。
· 左右子树返回值都非空，说明两个目标节点分居两侧，当前节点即为答案。
· 只需要一次 DFS，无需额外存储路径。

附：迭代写法（父指针 + 祖先集合）

classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){Map<TreeNode,TreeNode>parent=newHashMap<>();Deque<TreeNode>stack=newArrayDeque<>();parent.put(root,null);stack.push(root);// 遍历整棵树，记录每个节点的父节点while(!parent.containsKey(p)||!parent.containsKey(q)){TreeNodenode=stack.pop();if(node.left!=null){parent.put(node.left,node);stack.push(node.left);}if(node.right!=null){parent.put(node.right,node);stack.push(node.right);}}// 记录 p 到根的所有祖先Set<TreeNode>ancestors=newHashSet<>();while(p!=null){ancestors.add(p);p=parent.get(p);}// 从 q 向上找第一个在 p 祖先集合中的节点while(!ancestors.contains(q)){q=parent.get(q);}returnq;}}

迭代写法时间复杂度 O(n)，空间复杂度 O(n)，适合不想用递归或树很深的情况。