当前位置：首页 > article >正文

2025年- H48-Lc156 --236. 二叉树的最近公共祖先(递归、深搜）--Java版

article 2025/7/1 4:41:36

1.题目描述

在这里插入图片描述

递归终止条件：

如果当前节点 root 为 null，表示到达了叶子节点的空子树；

如果当前节点是 p 或 q，就返回它（因为从这里可以回溯寻找公共祖先）。

2.思路

（1）如果当前节点为 null，或者等于 p 或 q，直接返回。应该返回 root，因为找到了 p 或 q，不能返回 null
（2）在左子树中查找 p 和 q
（3）在右子树中查找 p 和 q
（4）如果左右子树都找到了，说明 p 和 q 分别在左右子树中，当前节点是最近公共祖先
（5）如果只在左子树找到了结果
（6）否则返回右子树的结果（可能是 null 或找到的节点）

3.代码实现

 class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}}
public class H236 {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 后序遍历 + 递归方式// 如果当前节点是 null，或者当前节点就是 p 或 q，则返回当前节点
//        递归终止条件：
//
//        如果当前节点 root 为 null，表示到达了叶子节点的空子树；
//
//        如果当前节点是 p 或 q，就返回它（因为从这里可以回溯寻找公共祖先）。if(root==null||root==p||root==q){return root;}//递归遍历左右子树TreeNode left=lowestCommonAncestor(root.left,p,q);TreeNode right=lowestCommonAncestor(root.right,p,q);// 如果左子树和右子树都找到了非空结果，说明 p 和 q 分别在左右子树中// 当前节点 root 就是最近公共祖先if(left!=null&&right!=null){// p 和 q 分别在左右子树return root;}// 如果只有一边找到了非空结果，返回那一边（继续向上传递结果）if(left!=null){return left;}else{return right;}}public static void main(String[] args){H236 test=new H236();TreeNode node11=new TreeNode(4,null,null);TreeNode node10=new TreeNode(7,null,null);TreeNode node7=new TreeNode(8,null,null);TreeNode node6=new TreeNode(0,null,null);TreeNode node5=new TreeNode(2,node10,node11);TreeNode node4=new TreeNode(4,null,null);TreeNode node3=new TreeNode(1,node6,node7);TreeNode node2=new TreeNode(5,node4,node5);TreeNode head=new TreeNode(3,node2,node3);TreeNode res=test.lowestCommonAncestor(head,node2,node3);System.out.print(res.val);}}